Submission #1262991

#TimeUsernameProblemLanguageResultExecution timeMemory
1262991khanghb2006Knapsack (NOI18_knapsack)C++20
73 / 100
1095 ms488 KiB
#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, -1e18); dp[0] = 0; for (int i = 0; i < N; i++) { int v, w, k; cin >> v >> w >> k; // chia thành các lớp theo modulo w for (int r = 0; r < w; r++) { deque<pair<ll,int>> dq; // dq lưu (giá trị, chỉ số j/w) for (int j = r, idx = 0; j <= S; j += w, idx++) { ll base = dp[j] - 1LL * idx * v; // bỏ những thằng ra khỏi cửa sổ while (!dq.empty() && dq.front().second < idx - k) dq.pop_front(); // cập nhật bằng front if (!dq.empty()) { dp[j] = max(dp[j], dq.front().first + 1LL * idx * v); } // push current while (!dq.empty() && dq.back().first <= base) dq.pop_back(); dq.push_back({base, idx}); } } } cout << *max_element(dp.begin(), dp.end()) << "\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...