Submission #1179012

#TimeUsernameProblemLanguageResultExecution timeMemory
1179012genocidedheusKnapsack (NOI18_knapsack)C++20
73 / 100
1096 ms16244 KiB
#include <bits/stdc++.h> using namespace std; int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); long long n,s,w,v,a,k,i,j; vector<long long> weight; vector<long long> value; cin >> s >> n; while(n--){ cin >> v >> w >> a; k=1; while(k<=a){ weight.push_back(w*k); value.push_back(v*k); a-=k; k*=2; } if(a>0){ weight.push_back(w*a); value.push_back(v*a); } } vector<long long> DP(s+1,0); for(i=0;i<weight.size();i++){ for(j=s;j>=weight[i];j--){ DP[j]=max(DP[j],DP[j-weight[i]]+value[i]); } } cout << DP[s] << endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...