Submission #1203643

#TimeUsernameProblemLanguageResultExecution timeMemory
1203643timeflewKnapsack (NOI18_knapsack)C++20
73 / 100
1095 ms560 KiB
//gpt4 #include <bits/stdc++.h> using namespace std; using ll = long long; int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int S, N; cin >> S >> N; vector<ll> dp(S+1, 0); for(int i = 0; i < N; i++){ ll V, W, K; cin >> V >> W >> K; // 1) If effectively infinite, do complete‐knapsack if (K * W >= S) { for(int j = W; j <= S; ++j){ dp[j] = max(dp[j], dp[j - W] + V); } } // 2) Otherwise do bounded‐knapsack via sliding‐window else { // process each residue class modulo W for(int r = 0; r < W; r++){ deque<pair<ll,int>> dq; // iterate k = 0,1,2,... with position pos = r + k*W for(int k = 0, pos = r; pos <= S; ++k, pos += W){ ll val = dp[pos] - k * V; // drop out‐of‐window while (!dq.empty() && k - dq.front().second > K) dq.pop_front(); // maintain decreasing dq by val while (!dq.empty() && dq.back().first <= val) dq.pop_back(); dq.emplace_back(val, k); // front of dq is best; restore value dp[pos] = dq.front().first + k * V; } } } } cout << dp[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...