Submission #1160860

#	Time	Username	Problem	Language	Result	Execution time	Memory
1160860		nicon9	Knapsack (NOI18_knapsack)	C++20	73 / 100	1093 ms	2836 KiB

knapsack

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

#define ll long long

const int mxs = 2001;

int main() {
    int s, n;
    cin >> s >> n;
    vector<pair<pair<ll, int>, int>> item(n);
    for(int i = 0 ; i < n ; i++){
        cin >> item[i].first.first >> item[i].first.second >> item[i].second;
        //. >> value               >> weight               >> number
    }

    //1. We can safely assume WK < S, and thus we decrease K_i (note that s < 2000, actually!)
    for(int i = 0 ; i < n ; i++){
        item[i].second = min(item[i].second, s / item[i].first.second);
    }

    vector<int> dp(mxs);
    for(int i = 0 ; i < n ; i++){
        for(int pos = mxs - 1 ; pos > -1 ; pos--){
            for(int num = 1 ; num <= item[i].second ; num++){
                if(pos + num * item[i].first.second < mxs) {
                    dp[pos + num * item[i].first.second] = max(0LL + dp[pos + num * item[i].first.second],
                                                                0LL + dp[pos] + num * item[i].first.first);
                }

            }
        }
    }

    for(int i = 0 ; i < s + 1 ; i++){
        //cout << dp[i] << " ";
    }//cout << endl;
    cout << dp[s] << endl;
}

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