Submission #1223926

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

knapsack

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

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

int ans = 0;

int main(void){
   // freopen("input.txt", "r", stdin);
    cin>>w>>n;
    stuff.assign(n, {});
    stuffV.assign(n, 0);
    dp.assign(w+1, 0);
    times.assign(w+1, 0);

    for(int i = 0; i<n; i++){
        cin>>stuffV[i]>>stuff[i].first>>stuff[i].second;
    }

    for(int i = 0; i<n; i++){
        times.assign(w+1, 0);
        for(int 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)){
                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;
}

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