Submission #649613

#	Time	Username	Problem	Language	Result	Execution time	Memory
649613		MEGalodon	Knapsack (NOI18_knapsack)	C++14	100 / 100	303 ms	19372 KiB

knapsack

#include <bits/stdc++.h>
#define MAXN 2001
#define ii pair<int, int>
using namespace std;
vector<ii> W[MAXN];
int dp[MAXN][MAXN];
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int S, N;
    cin>>S>>N;
    for( int i{1} ; i <= N ; ++i ){
        int v, w, k;
        cin>>v>>w>>k;
        W[w].push_back({v, k});
    }
    for( int i{1} ; i <= S ; ++i ){ sort(W[i].begin(), W[i].end(), [&](ii a, ii b){ return a.first > b.first; }); }
    memset(dp, 0, sizeof(0));
    for( int i{1} ; i <= S ; ++i ){
        for( int s{1} ; s <= S ; ++s ){
            int curW = s, curV = 0;
            int ret = dp[s][i-1];
            for( auto x : W[i] ){
                int v = x.first;
                int k = x.second;
                while( curW-i >= 0 && k ){
                    curW -= i;
                    k--;
                    curV += v;
                    ret = max(ret, dp[curW][i-1]+curV);
                }
            }
            dp[s][i] = ret;
        }
    }
    //you can't see how your values are progressing
    //you think it should go a certain way, but if there is an error you can't spot it by printing the super large table
    cout<<dp[S][S]<<'\n';
    return 0;
}

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