Submission #1179012

#	Time	Username	Problem	Language	Result	Execution time	Memory
1179012		genocidedheus	Knapsack (NOI18_knapsack)	C++20	73 / 100	1096 ms	16244 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;
 
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    long long n,s,w,v,a,k,i,j;
    vector<long long> weight;
    vector<long long> value;
    cin >> s >> n;
    while(n--){
        cin >> v >> w >> a;
        k=1;
        while(k<=a){
            weight.push_back(w*k);
            value.push_back(v*k);
            a-=k;
            k*=2;
        }
        if(a>0){
            weight.push_back(w*a);
            value.push_back(v*a);
        }
    }
    vector<long long> DP(s+1,0);
    for(i=0;i<weight.size();i++){
        for(j=s;j>=weight[i];j--){
            DP[j]=max(DP[j],DP[j-weight[i]]+value[i]);
        }
    }
    cout << DP[s] << endl;
}

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