Submission #1228551

#TimeUsernameProblemLanguageResultExecution timeMemory
1228551mn3mKnapsack (NOI18_knapsack)C++20
73 / 100
1095 ms2632 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++)dp[idx % 2][cur] = dp[(idx + 1) % 2][cur]; if (k[idx] * w[idx] >= s) for (int cur = w[idx]; cur <= s; cur++)dp[idx % 2][cur] = max( dp[idx % 2][cur], dp[idx % 2][cur - w[idx]] + v[idx]); else { for (int cur = s; cur >= 0; cur--) { int mx = min(k[idx], cur / w[idx]); for (int in = 1; in <= mx; in++)dp[idx % 2][cur] = max( dp[idx % 2][cur], dp[(idx + 1) % 2][cur - in * w[idx]] + in * v[idx]); } } } 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...