Submission #1195428

#TimeUsernameProblemLanguageResultExecution timeMemory
1195428timeflewKnapsack (NOI18_knapsack)C++20
73 / 100
1095 ms2992 KiB
#include<bits/stdc++.h> using namespace std; #define ll long long #define ff first #define ss second #define int long long const int mxS=2e3; ll dp[mxS+1]; int32_t main() { ios::sync_with_stdio(0); cin.tie(0); int s, n; cin>>s>>n; vector<array<ll, 3>> v(n); for(int i=0; i<n; i++) { cin>>v[i][0]>>v[i][1]>>v[i][2];//v, w, k } fill(dp, dp+mxS+1, -1e18); dp[0]=0; ll ans=0; for(int i=0; i<n; i++) { ll use=v[i][2]; for(int j=1; use>0; j*=2) { ll x=min(use, j)*v[i][1]; ll val=1ll*min(use, j)*v[i][0]; for(int k=s; k>=x; k--) { dp[k]=max(dp[k], dp[k-x]+val); ans=max(ans, dp[k]); } use-=min(use, j); } } cout<<ans; 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...