Submission #895252

#	Time	Username	Problem	Language	Result	Execution time	Memory
895252		codexistent	Knapsack (NOI18_knapsack)	C++17	12 / 100	20 ms	31780 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for(int i = a; i <= b; i++)
#define ll long long
#define mp make_pair
#define f first
#define s second

int main(){
    int S, N;
    cin >> S >> N;
    map<int, multiset<pair<int, int>>> T;
    FOR(i, 0, N - 1){
        int v, w, ct;
        cin >> v >> w >> ct;
        if(T.find(w) == T.end()){
            multiset<pair<int, int>> vv;
            T.insert(mp(w, vv));
        }
        T[w].insert(mp(-v, ct));
    }

    ll dp[S + 1][S + 1], R = 0;
    FOR(i, 0, S) FOR(j, 0, S) dp[i][j] = 0;
    int ofs = 1;
    for(auto t : T){
        FOR(i, 1, S){
            auto it = t.s.begin();
            int v = -(t.s.begin()->f), ct = t.s.begin()->s;
            ll vs = 0;
            for(int w = t.f; w <= i; w += t.f){
                vs += v;
                dp[ofs][i] = max(dp[ofs][i], dp[ofs - 1][i - w] + vs);
                R = max(R, dp[ofs][i]);
                ct--;
                if(ct == 0){
                    if(++it == t.s.end()) break;
                    v = -(it->f), ct = it->s;
                }
            }
        }
        ofs++;
    }

    cout << R << endl;
}

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