Submission #1218467

#TimeUsernameProblemLanguageResultExecution timeMemory
1218467_llKnapsack (NOI18_knapsack)C++20
73 / 100
1096 ms3144 KiB
#pragma GCC optimize("O3,unroll-loops,inline") #include<bits/stdc++.h> using namespace std; typedef int ll; ll 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(); } }; 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; 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; } } cout << dp[ant][s] << "\n"; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...