Submission #1172408

#TimeUsernameProblemLanguageResultExecution timeMemory
1172408dbekarysKnapsack (NOI18_knapsack)C++20
12 / 100
0 ms328 KiB
#include <bits/stdc++.h> using namespace std; //vector<int>v[N]; int dp[10007][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<count;j++){ if(a[i]*(j+1)<=m) v1.push_back(a[i]); if(b[i]*(j+1)<=m) v2.push_back(b[i]); } } for(int i=1;i<=v1.size();i++){ for(int j=1;j<=m;j++){ dp[i][j]=dp[i-1][j]; if(v1[i-1]<=j){ dp[i][j]=max(dp[i][j],dp[i-1][j-v1[i-1]]+v2[i-1]); } } } cout<< dp[v1.size()][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...