Submission #1195423

#TimeUsernameProblemLanguageResultExecution timeMemory
1195423timeflewKnapsack (NOI18_knapsack)C++20
73 / 100
1093 ms2632 KiB
//test by gpt 4 #include <bits/stdc++.h> using namespace std; #define ll long long int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int S, N; cin >> S >> N; struct Item { ll v, w, k; }; vector<Item> items(N); for (int i = 0; i < N; i++) { cin >> items[i].v >> items[i].w >> items[i].k; } // dp[x] = max total value with weight exactly x const ll NEG_INF = LLONG_MIN / 4; vector<ll> dp(S+1, NEG_INF); dp[0] = 0; for (auto &it : items) { ll V = it.v, W = it.w, K = it.k; ll rem = K; // binary‐split the K copies into sums of powers of two for (ll batch = 1; rem > 0; batch <<= 1) { ll take = min(batch, rem); rem -= take; ll weight = take * W; ll value = take * V; if (weight > S) continue; // 0–1 knapsack for this “batch” chunk for (int x = S; x >= weight; x--) { if (dp[x - weight] != NEG_INF) { dp[x] = max(dp[x], dp[x - weight] + value); } } } } // answer = best over all weights ≤ S ll ans = 0; for (int x = 0; x <= S; x++) { ans = max(ans, dp[x]); } cout << ans << "\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...