Archives
Trending
Support
Login
clear text
XML
Django
JavaScript
MATLAB
C
C++
C#
Python
SQL
Shell
Bash
Markdown
YAML
JSON
HTML
CSS
PHP
Java
Ruby
Go
Rust
Swift
Kotlin
Arduino
TypeScript
Perl
Autohotkey
Lua
SQF
R
Scala
Haskell
Groovy
Dart
Clojure
VB.NET
Objective-C
PowerShell
Bash
CoffeeScript
Verilog
#include
#include
#include
#include
#include
using namespace std; int n, w; typedef long long ll; ll memo[105][100005]; ll weight[105]; ll value [105]; ll ks(int i,int value_left){ if(value_left == 0 ){ return 0; } if(i == n ){ return 2e18; } if(memo[i][value_left] != -1){ return memo[i][value_left]; } ll result = 2e18; result = min(result,ks(i+1,value_left)); if(value_left - value[i] >= 0){ result = min(result, ks(i+1,value_left -value[i]) + weight[i]); } return memo[i][value_left]= result; } int main() { cin >> n >> w; for (int i = 0; i < n; i++) { cin >> weight[i] >> value [i]; } for (int i = 0; i < 105; i++) { for (int j = 0; j < 100005; j++) { memo[i][j] = -1; } } ll rez = 0; for (int i = 0; i < 100005; i++) { if(ks(0,i) <= w){ rez = i; } } cout << rez; }
Mark as private (unlisted)
for 30 minutes
for 6 hours
for 1 day
for 1 week
for 1 month
for 1 year
everlasting (like CCCP)