| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 794322 | theghostking | Knapsack (NOI18_knapsack) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define int long long
int dp[2005][2005];
int search(int i, int remW, vector<pair<int,int>>& kp, int total){
if (i == total) return 0;
if (remW == 0) return 0;
if (dp[i][remW] != -1) return dp[i][remW];
if (kp[i].first <= remW){
return dp[i][remW] = max(search(i+1,remW,kp,total),search(i+1,remW-kp[i].first,kp,total)+kp[i].second);
}
else{
return dp[i][remW] = search(i+1,remW,kp,total);
}
}
signed main() {
memset(dp,-1,sizeof(dp));
int s,n;
cin >> s >> n;
vector<int> arr[2000];//offset weight by one for now
for (int i = 0; i<n; i++){
int v,w,k;
cin >> v >> w >> k;
k = min(2000,k);
w--;
int sz1 = arr[w].size();
int left = min(2000-sz1,k);
for (int j = 0; j<left; j++){
arr[w].push_back(v);
}
}
int total = 0;
vector<pair<int,int>> kp;
for (int i = 0; i<2000; i++){
int sz = arr[i].size();
total += sz;
for (int j = 0; j<sz; j++){
kp.push_back({i+1,arr[i][j]}); //weight,value
}
}
cout << search(0,s,kp,total) << '\n';
return 0;
}