# | TimeUTC-0 | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
486905 | YHC2538 | Knapsack (NOI18_knapsack) | C++14 | 118 ms | 3632 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;
void _debug(){cerr<<'\n';}
template<typename A,typename...B>
void _debug(A a,B...b){cerr<<a<<' ',_debug(b...);}
#define debug(args...) cerr<<"("<<(#args)<<"): ", _debug(args);
#define pii pair<int,int>
#define all(x) (x).begin(),(x).end()
typedef long long ll;
const int N=2005;
ll dp[N];
int main(){
int s,n; cin>>s>>n;
vector<vector<pii>> weight(s+1);
for(int i=1;i<=n;i++){
int v,w,k; cin>>v>>w>>k;
weight[w].push_back({v,k});
}
for(int i=1;i<=s;i++){
sort(all(weight[i]),greater<pii>());
if(weight[i].size()==0) continue;
int id=0; //next item with weight i
for(int j=1;j*i<=s;j++){
if(id>=weight[i].size()) break;
for(int k=s;k>=i;k--){
dp[k]=max(dp[k],dp[k-i]+weight[i][id].first);
}
if(--weight[i][id].second==0) id++;
}
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |