제출 #1219313

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1219313		_ll	Knapsack (NOI18_knapsack)	C++20	12 / 100	1095 ms	94200 KiB

knapsack

#include<bits/stdc++.h>
using namespace std;
typedef int ll;
ll dp[2][2001];

struct fil{ 
    ll lf = 2000, rf = lf, lM = lf, rM = rf, f[6001], M[6001];
    ll size(){
        return rf - lf;
    }
    ll ma(){
        return M[lM];
    }
    void push(ll vl){ // assintótica O(1)
        while(rM > lM && M[rM - 1] < vl) 
            rM--;
        f[rf++] = M[rM++] = vl;
    }
    void pop(){ // O(1)
        if(M[lM] == f[lf]) lM++;
        lf++;
    }
};

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    ll s, n, ant = 0; cin >> s >> n;
    for(ll i = 0; i < n; ant = 1 - ant, i++){ // Obra de Arte, pena q talento
        ll v, w, q; cin >> v >> w >> q;
        vector<fil> fs(w); // resposta de cada fila mod m
        vector<ll> del(w); // delta para cada fila mod m
        for(ll j = 0; j <= s; j++){
            ll r = j % w;                    // deve ser a coisa mais lenta nesse laco
            fs[r].push(dp[ant][j] - del[r]); // resposta no nó sem colocar nenhum item
            dp[1 - ant][j] = fs[r].ma() + del[r];
            if(fs[r].size() == q + 1) // garante que nunca vou remover de uma pilha vazia
                fs[r].pop();
            del[r] += v; // ultima coisa a fazer
        }
    }
    cout << dp[ant][s] << "\n";
}

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