Submission #1223932

#	Time	Username	Problem	Language	Result	Execution time	Memory
1223932		opeleklanos	Knapsack (NOI18_knapsack)	C++20	12 / 100	1 ms	328 KiB

knapsack

#include <iostream>
#include <vector>
using namespace std;

#define ll long long

vector<pair<ll, ll>> stuff;
vector<ll> stuffV;
vector<ll> dp;
vector<ll>times;
ll w, n;

ll ans = 0;

int main(void){
    //freopen("input.txt", "r", stdin);
    cin>>w>>n;
    stuff.assign(n, {});
    stuffV.assign(n, 0);
    dp.assign(w+1, -1);
    times.assign(w+1, 0);
    dp[0] = 0;
    for(ll i = 0; i<n; i++){
        cin>>stuffV[i]>>stuff[i].first>>stuff[i].second;
    }

    for(ll i = 0; i<n; i++){
        times.assign(w+1, 0);
        for(ll j = stuff[i].first; j<=w; j++){
            if((dp[j] < dp[j - stuff[i].first] + stuffV[i]) && (times[j-stuff[i].first] < stuff[i].second) && (dp[j - stuff[i].first] != -1)){
                times[j] = times[j-stuff[i].first] + 1;
                dp[j] = dp[j - stuff[i].first] + stuffV[i];
            }

            ans = max(ans, dp[j]);
        }
    }
    cout<<ans<<endl;
    return 0;
}

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