Submission #895280

#	Time	Username	Problem	Language	Result	Execution time	Memory
895280		codexistent	Knapsack (NOI18_knapsack)	C++14	100 / 100	170 ms	46140 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for(ll i = a; i <= b; i++)
#define ll long long
#define mp make_pair
#define f first
#define s second
 
int main(){
    ll S, N;
    cin >> S >> N;
    map<ll, multiset<pair<ll, ll>>> T;
    FOR(i, 0, N - 1){
        ll v, w, ct;
        cin >> v >> w >> ct;
        if(ct == 0) continue;
        if(T.find(w) == T.end()){
            multiset<pair<ll, ll>> 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] = -1;
    dp[0][0] = 0;
    ll ofs = 1;
    for(auto t : T){
        //cout << t.f << endl;
        FOR(i, 0, t.f - 1) dp[ofs][i] = dp[ofs - 1][i];
        FOR(i, t.f, S){
            dp[ofs][i] = dp[ofs - 1][i];
            auto it = t.s.begin();
            ll v = -(t.s.begin()->f), ct = t.s.begin()->s;
            ll vs = 0;
            for(ll w = t.f; w <= i; w += t.f){
                vs += v;
                if(dp[ofs - 1][i - w] != -1) {
                    dp[ofs][i] = max(dp[ofs][i], dp[ofs - 1][i - w] + vs);
                    R = max(R, dp[ofs][i]);
                }
                //cout << " " << i << " ~ " << ct << " " << v << endl;
                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: 17 / 17
• Subtask 3: 20 / 20
• Subtask 4: 24 / 24
• Subtask 5: 27 / 27