Submission #973206

#TimeUsernameProblemLanguageResultExecution timeMemory
973206SeenSiravitKnapsack (NOI18_knapsack)C++14
29 / 100
2 ms348 KiB
#include<bits/stdc++.h> #define ll long long using namespace std; const int mxN = 1e5 + 5 , mxS = 2000 + 5; int n,s; ll v[mxN]; int w[mxN] , k[mxN]; ll mem[mxS]; int main(){ ios::sync_with_stdio(0),cin.tie(0); cin>> s >> n; for(int i=1;i<=n;i++) cin>> v[i] >> w[i] >> k[i] , k[i] = min(k[i] , s/w[i]); for(int i=1;i<=n;i++){ vector<pair<ll,int>> dp(s+1 , {0,0}); for(int cap=1;cap<=s;cap++){ dp[cap] = {mem[cap] , 0}; if(cap >= w[i]){ int l = cap - w[i]; int cnt = min(k[i] , dp[l].second + 1); int rm = cap - w[i] * cnt; pair<ll,int> candidate = {mem[rm] + v[i]*cnt , cnt}; if(candidate.first > dp[cap].first){ dp[cap] = candidate; } } } for(int cap=1;cap<=s;cap++) mem[cap] = dp[cap].first; } cout<< mem[s]; return 0; }
#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...