Submission #1014516

#	Time	Username	Problem	Language	Result	Execution time	Memory
1014516		dizzytaps	Knapsack (NOI18_knapsack)	C++14	37 / 100	120 ms	262144 KiB

knapsack

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

int main(){
    int s,n;
    cin>>s>>n;
    vector<int> values;
    vector<int> weights;
    for(int i=0;i<n;i++){
        int val,weight,k;
        cin>>val>>weight>>k;
        for(int i=0;i<k;i++){
            values.push_back(val);
            weights.push_back(weight);
        }
    }

    vector<vector<int>> dp(s+1,vector<int>(values.size()+1,0));
    
    for(int i=1;i<=s;i++){
        for(int j=1;j<=values.size();j++){
            dp[i][j]=dp[i][j-1];
            if(i-weights[j-1]>=0) dp[i][j]=max(dp[i][j],dp[i-weights[j-1]][j-1]+values[j-1]);
        }
    }


    cout<<dp[s][values.size()]<<endl;
}

Compilation message (stderr)

knapsack.cpp: In function 'int main()':
knapsack.cpp:21:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |         for(int j=1;j<=values.size();j++){
      |                     ~^~~~~~~~~~~~~~~

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