Submission #1172423

#TimeUsernameProblemLanguageResultExecution timeMemory
1172423dbekarysKnapsack (NOI18_knapsack)C++20
12 / 100
46 ms8264 KiB
#include <bits/stdc++.h> using namespace std; #define int long long const long long inf=1e18; int dp[1000007]; 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]); } } for(int i=0;i<=1000000;i++){ dp[i]=inf; } dp[0]=0; for(int i=0;i<v1.size();i++){ for(int j=1000000-v2[i];j>=0;j--){ dp[j+v2[i]]=min(dp[j]+v1[i],dp[j+v2[i]]); } } for(int i=1000000;i>=0;i--){ if(dp[i]<=m){ cout<< i; break; } } }
#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...