Submission #648496

#	Time	Username	Problem	Language	Result	Execution time	Memory
648496		imaginary_unit	Knapsack (NOI18_knapsack)	C++17	73 / 100	1094 ms	8412 KiB

knapsack

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

const int MAX_N=1e5, MAX_S=2000;

int s, n;
int v[MAX_N], w[MAX_N], k[MAX_N];
int dp[MAX_S+1];

unordered_map<int, int> used[MAX_S+1];

int main()
{
    cin >> s >> n;
    for(int i=0; i<n; i++){
        cin >> v[i] >> w[i] >> k[i];
    }
    dp[0]=0;
    for(int tot=1; tot<=s; tot++){
        int max_value=dp[tot-1], max_item=(-1);
        for(int i=0; i<n; i++){
            if(tot-w[i]>=0 && (!used[tot-w[i]].count(i) || used[tot-w[i]][i]<k[i]) && dp[tot-w[i]]+v[i]>max_value){
                max_value=dp[tot-w[i]]+v[i];
                max_item=i;
            }
        }
        dp[tot]=max_value;
        if(max_item==(-1)){
            used[tot]=used[tot-1];
        }
        else{
            used[tot]=used[tot-w[max_item]];
            used[tot][max_item]++;
        }
    }
    cout << dp[s];
}

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