Submission #1221342

#	Time	Username	Problem	Language	Result	Execution time	Memory
1221342		gabenelli	Knapsack (NOI18_knapsack)	C++20	73 / 100	1095 ms	2732 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;

#define int     long long
#define sz(x)   (int)size(x)
#define all(x)  begin(x), end(x)

struct MaxQueueTunada{ // Based on max-queue2.cpp taught in class
    int ti, tf, delta;
    deque< pair<int,int> > Q; // (val, time)
    MaxQueueTunada(){
        delta = ti = tf = 0;
        Q.clear();
    }
    void push(int x){
        x -= delta;
        while(!Q.empty() && Q.back().first <= x)
            Q.pop_back();
        Q.push_back(pair<int,int>(x, tf++));
    }
    void pop(){
        if(!Q.empty() && ti == Q.front().second)
            Q.pop_front();
        ti++;
    }
    int max(){ return (ti == tf ? 0ll : Q.front().first + delta); }
    void addAll(int d){ delta += d; }
};

const int MAXN = 112345;
int C, N, V[MAXN], W[MAXN], K[MAXN];

void solve(){
    cin >> C >> N;
    for(int i = 1; i <= N; ++i)
        cin >> V[i] >> W[i] >> K[i];
    vector<int> dp_old(C + 1), dp_at = dp_old;
    for(int i = 1; i <= N; ++i){
        for(int rem = 0; rem <= min(C, W[i] - 1); ++rem){ // For each possible remainder value
            MaxQueueTunada Q;
            int ini = rem + ((C - rem) / W[i]) * W[i]; // place to start the window
            int lo = ini; // leftmost index of the sliding window
            for(int c = ini; c >= 0; c -= W[i]){ // Calculate dp_at[c] for each c in class 'rem'
                
                if(c < ini){
                    Q.pop();
                    Q.addAll(-V[i]);
                    //cerr << "popei a queue e decrementei " << V[i] << " de todo mundo\n";
                }
                
                dp_at[c] = dp_old[c]; // dp[i][c] = dp[i-1][c]
                while(lo >= 0 && (c - lo) / W[i] <= K[i]){ // Maintaining feasible sliding window
                    Q.push( V[i] * ((c - lo) / W[i]) + dp_old[lo]);
                    lo -= W[i];
                }
                
                //cerr << "sliding window esta em [" << lo + W[i] << ", " << c << "]\n";
                
                dp_at[c] = Q.max();
                
                //cerr << "O melhor foi " << dp_at[c] << "\n\n";
            }
        }
        dp_old = dp_at;
    }
    cout << dp_at[C] << '\n';
}

signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    //int t; cin>>t; while(t--)
    solve();
    return 0;
}

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