Submission #1218496

#	Time	Username	Problem	Language	Result	Execution time	Memory
1218496		_ll	Knapsack (NOI18_knapsack)	C++20	100 / 100	896 ms	6712 KiB

knapsack

#include<bits/stdc++.h>
using namespace std;
typedef int ll;
ll s, n, ant = 0, dp[2][2001];

struct fil{ // pra deixar menor assumo que nunca vou remover de uma pilha vazia
    deque<ll> f, M;
    ll ma(){
        return M.front();
    }
    void push(ll vl){ // assintótica O(1)
        while(M.size() && M.back() < vl) // valores iguais precisam (<)
            M.pop_back(); // ser colocados todas as vezes que aparecem
        f.push_back(vl), M.push_back(vl);
    }
    void pop(){ // O(1)
        if(M.front() == f.front()) M.pop_front();
        f.pop_front();
    }
};

void faz(ll v, ll w, ll q){
    fil fs[w];                                  // resposta de cada fila mod m
    vector<ll> del(w);                           // delta para cada fila mod m
    for(ll j = 0, r = 0; j <= s; r++, j++){
        if(r == w) r = 0;                       // evito usar % (por ser lento)
        fs[r].push(dp[ant][j] - del[r]);         // resposta sem colocar o item
        dp[1 - ant][j] = fs[r].ma() + del[r];
        if(fs[r].f.size() == q + 1)   // garante não remover de uma pilha vazia
            fs[r].pop();
        del[r] += v;                                  
    }
    ant = 1 - ant;
}

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

     cin >> s >> n;
    vector<array<ll, 4>> Mv(n), mw(n); // menos de 32 10 ^6
    vector<ll> f(n);
    for(ll i = 0; i < n; i++){          // completa heuristica
        cin >> Mv[i][0] >> Mv[i][1] >> Mv[i][2];
        mw[i] = {Mv[i][1], -Mv[i][0], -Mv[i][2], i};
        Mv[i][3] = i, Mv[i][1] *= -1;
    }
    sort(Mv.rbegin(), Mv.rend()); // aqui pego os 2 * 10 ^ 4 maiores
    sort(mw.begin(), mw.end()); // Obra de Arte, pena q talento
    for(ll i = 0; i < min(n, (ll) 2e3); i++){ // os d maior valor
        f[Mv[i][3]] = 1;
        faz(Mv[i][0], -Mv[i][1], Mv[i][2]);
    }
    ll q = 0;
    for(ll i = 0; q < 2e3 && i < n; i++) if(!f[mw[i][3]]){ // os d menor peso
        q += (f[mw[i][3]] = 1);
        faz(-mw[i][1], mw[i][0], -mw[i][2]);
    }
    cout << dp[ant][s] << "\n";
}

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