Submission #1218471

#	Time	Username	Problem	Language	Result	Execution time	Memory
1218471		_ll	Knapsack (NOI18_knapsack)	C++20	73 / 100	1095 ms	3108 KiB

knapsack

#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(){
    ll s, n, ant = 0; scanf("%d %d", &s, &n);
    for(ll i = 0; i < n; ant = 1 - ant, i++){      // Obra de Arte, pena q talento
        ll v, w, q; scanf("%d %d %d", &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;                                  
        }
    }
    printf("%d\n", dp[ant][s]);
}

Compilation message (stderr)

knapsack.cpp: In function 'int main()':
knapsack.cpp:23:28: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |     ll s, n, ant = 0; scanf("%d %d", &s, &n);
      |                       ~~~~~^~~~~~~~~~~~~~~~~
knapsack.cpp:25:26: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |         ll v, w, q; scanf("%d %d %d", &v, &w, &q);
      |                     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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