Submission #877943

#	Time	Username	Problem	Language	Result	Execution time	Memory
877943		codexistent	Knapsack (NOI18_knapsack)	C++14	73 / 100	1039 ms	604 KiB

knapsack

#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, V, W, K;
    cin >> S >> N;
 
    int DP[2][S + 1]; // DP[items 1...n][shopping cart size used]
    FOR(n, 0, N) FOR(s, 0, S) DP[0][s] = 0ll;
    FOR(n, 1, N){
        cin >> V >> W >> K;
        if(W * K >= S){
            FOR(s, 0, S) {
                DP[n % 2][s] = DP[(n - 1) % 2][s];
                if(s - W >= 0) DP[n % 2][s] = max(DP[n % 2][s], DP[n % 2][s - W] + V);
            }
        }else{
            K = min(S, K);
            FOR(a, 0, W - 1){
                deque<int> sw, indx; // sliding window deck
                for(int s = a, i = 0; s <= S; s += W, i++){
                    DP[n % 2][s] = DP[(n - 1) % 2][s];
                    if(!sw.empty()) DP[n % 2][s] = max(DP[n % 2][s], sw.front() + V*i);
                    
                    // update deck
                    if(!sw.empty() && i - indx.front() >= K) {
                        sw.pop_front();
                        indx.pop_front();
                    }
                    int upd = DP[(n - 1) % 2][s] - V*i;
                    while(!sw.empty() && sw.back() < upd) sw.pop_back(), indx.pop_back();
                    sw.push_back(upd), indx.push_back(i);
                }
            }
        }
    }
 
    int R = 0;
    FOR(s, 0, S) R = max(R, DP[N % 2][s]);
 
    cout << R << endl;
}

• Subtask 1: 12 / 12
• Subtask 2: 17 / 17
• Subtask 3: 20 / 20
• Subtask 4: 24 / 24
• Subtask 5: 0 / 27