Submission #1228452

#TimeUsernameProblemLanguageResultExecution timeMemory
1228452mn3mKnapsack (NOI18_knapsack)C++20
73 / 100
1095 ms2788 KiB
#pragma GCC optimize ("O3") #pragma GCC optimize ("unroll-loops") #pragma GCC optimize("-Ofast") #include<bits/stdc++.h> #define int long long #define pb push_back #define ceil(x,y) (x/y)+(x%y!=0)*((double)(1.0*x/y)<0?0:1) using namespace std; int MOD = 998244353; int MX = 1e15; int MN = -1e15; int s, n; int v[100002], w[100002], k[100002]; int dp[2][2002]; int32_t main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); // freopen("snakes.in","r",stdin); // freopen("snakes.out","w",stdout); int T = 1; // cin >> T; while (T--) { cin >> s >> n; for (int i = 0; i < n; i++) cin >> v[i] >> w[i] >> k[i]; memset(dp, -1, sizeof(dp)); for (int i = 0; i <= s; i++) dp[n%2][i] = 0; for (int idx = n-1;idx >= 0;idx--) for (int cur = 0; cur <= s; cur++) for (int i = 0; i <= min(k[idx],cur/w[idx]); i++) dp[idx%2][cur]=max(dp[idx%2][cur],dp[(idx+1)%2][cur-w[idx]*i]+v[idx]*i); cout<<dp[0][s]<<"\n"; } 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...