Submission #1172427

#TimeUsernameProblemLanguageResultExecution timeMemory
1172427dbekarysKnapsack (NOI18_knapsack)C++20
73 / 100
332 ms327680 KiB
#include <bits/stdc++.h> using namespace std; #define int long long const long long inf=1e18; int dp[2007]; signed main() { ios_base::sync_with_stdio(0); cin.tie(); int m,n; cin>> m>>n; bool ok = 0 ; if(n == 1) { ok = 1 ; } int a[n+1],b[n+1]; vector<int>v1,v2,k; for(int i=1,count;i<=n;i++){ cin>> b[i]>>a[i]>>count; if(ok) { int s = m / a[i] ; if(s >= count) { cout << b[i] * count ; } else { cout << b[i] * s ; } return 0; } k.push_back(count); for(int j=0;j<min(count,m);j++){ v1.push_back(a[i]); v2.push_back(b[i]); } } dp[0]=0; for(int i=0;i<v1.size();i++){ for(int j=m;j>=v1[i];j--){ dp[j]=max(dp[j],dp[j-v1[i]]+v2[i]); } } cout<< dp[m]; }
#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...