| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 877920 | codexistent | Knapsack (NOI18_knapsack) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <iostream>
#include <queue>
using namespace std;
#define FOR(i, a, b) for(int i = a; i <= b; i++)
#define FOR_EXC(i, a, b) for(int i = a; i < b; i++)
int main(){
int S, N;
long long V, W, K;
cin >> S >> N;
long long DP[N + 1][S + 1]; // DP[items 1...n][shopping cart size used]
FOR(n, 0, N) FOR(s, 0, S) DP[n][s] = 0ll;
FOR(n, 1, N){
cin >> V >> W >> K;
K = max(K, N);
deque<pair<long long, int>> sw; // sliding window deck
FOR(a, 0, W - 1){
for(int s = a, i = 0; s <= S; s += W, i++){
DP[n][s] = DP[n - 1][s];
if(!sw.empty()) DP[n][s] = max(DP[n][s], sw.front().first + V*i);
// update deck
if(!sw.empty() && i - sw.front().second >= K) {
sw.pop_front();
}
long long upd = DP[n - 1][s] - V*i;
while(!sw.empty() && sw.back().first < upd) sw.pop_back();
sw.push_back(make_pair(upd, i));
}
}
sw.clear();
}
long long R = 0;
FOR(s, 0, S) R = max(R, DP[N][s]);
cout << R << endl;
}