Submission #984675

#	Time	Username	Problem	Language	Result	Execution time	Memory
984675		Sandarach151	Knapsack (NOI18_knapsack)	C++17	73 / 100	137 ms	262144 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;

#define int long long

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int s, n;
    cin >> s >> n;
    int w[n+1], v[n+1], k[n+1];
    for(int i=1; i<=n; i++){
        cin >> v[i] >> w[i] >> k[i];
    }
    vector<vector<pair<int, int> > > ans(n+1, vector<pair<int, int> >(s+1));
    for(int i=0; i<=s; i++){
        ans[0][i] = {0, 0};
    }
    for(int i=1; i<=n; i++){
        for(int j=0; j<=s; j++){
            if(j>=w[i]){
                if(ans[i][j-w[i]].second < k[i]){
                    if(ans[i][j-w[i]].first+v[i] > ans[i-1][j].first) {
                        ans[i][j] = {ans[i][j-w[i]].first + v[i], ans[i][j-w[i]].second+1};
                    }
                    else{
                        ans[i][j] = {ans[i-1][j].first, 0};
                    }
                }
                else{
                    for(int kk=0; kk*w[i]<=j && kk<=k[i]; kk++){
                        if(ans[i-1][j-w[i]*kk].first+v[i]*kk > ans[i][j].first){
                            ans[i][j] = {ans[i-1][j-w[i]*kk].first+v[i]*kk, kk};
                        }
                    }
                }
            }
            else{
                ans[i][j] = ans[i-1][j];
            }
        }
    }
    // for(int i=-1; i<=s; i++){
    //     printf("%5d", i);
    // }
    // printf("\n");
    // for(int i=0; i<=n; i++){
    //     printf("%3d: ", i);
    //     for(int j=0; j<=s; j++){
    //         printf("%5d", ans[i][j].first);
    //     }
    //     printf("\n");
    // }
    cout << ans[n][s].first << '\n';
}

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