Submission #1242241

#TimeUsernameProblemLanguageResultExecution timeMemory
1242241wedonttalkanymoreKnapsack (NOI18_knapsack)C++20
100 / 100
220 ms1624 KiB
#pragma GCC optimize("O3") #pragma GCC optimize("Ofast,unroll-loops") #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt") #include <bits/stdc++.h> using namespace std; using ll = long long; // #define int long long #define pii pair<ll, ll> #define fi first #define se second const ll N = 1e5 + 5, inf = 1e18, mod = 1e9 + 7, block = 320; int s, n; int v[N], w[N], k[N]; int dp[N]; signed main() { ios::sync_with_stdio(false); cin.tie(0); cin >> s >> n; for (int i = 1; i <= n; i++) { cin >> v[i] >> w[i] >> k[i]; k[i] = min(k[i], 2000); } for (int i = 1; i <= n; i++) { for (int j = 1; k[i] > 0; j *= 2) { int now = min(j, k[i]); int val = now * v[i]; int weight = now * w[i]; if (weight > s) break; for (int x = s; x >= weight; x--) { if (x >= weight) dp[x] = max(dp[x], dp[x - weight] + val); } k[i] -= now; } } int ans = 0; for (int i = 0; i <= s; i++) { ans = max(ans, dp[i]); } 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...