Submission #1227686

#	Time	Username	Problem	Language	Result	Execution time	Memory
1227686		thesen	Knapsack (NOI18_knapsack)	C++20	49 / 100	3 ms	1864 KiB

knapsack

#include <bits/stdc++.h>
#define pb push_back
#define ll long long
#define vint vector <int>
#define vll vector <ll>
#define vbool vector<bool>
#define pairint pair<int,int>
#define pairll pair<ll,ll>
#define fi first
#define sc second
#define rever greater<ll>()
using namespace std;

struct dta{
    ll v, w, k;
};

void solve(ll tc){
    ll s, n; cin >> s >> n;

    vector<vector<pairll>> a(2001); ll v, w, k;
    while(n--){
        cin >> v >> w >> k;
        if(k > 2000){
            k = 2000;
        }
        a[w].pb({v, k});
    }
    for(int i = 1; i <= 2000; i++){
        sort(a[i].begin(), a[i].end(), greater<pairll>());
    }

    vector<dta> c(1); ll tot;
    for(int i = 1; i <= 2000; i++){
        tot = 0;
        for(pairll x : a[i]){
            if(tot >= s){
                break;
            }
            c.pb({x.fi, i, x.sc});
            tot += i*k;
        }
    }

    vector<vll> dp(c.size(), vll(s+1, 0));
    for(ll i = 1; i < c.size(); i++){
        for(ll j = 1; j <= s; j++){
            dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
            for(ll k = 1; k <= c[i].k; k++){
                if(j-c[i].w*k < 0){
                    break;
                }
                dp[i][j] = max(dp[i][j], dp[i-1][j-c[i].w*k] + c[i].v*k);
            }
        }
    }cout << dp[c.size()-1][s] << endl;
}

int main(){
    ll t; t = 1;
    for(int i = 1; i <= t; i++){
        solve(i);
    }
}

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