Submission #728510

#	Time	Username	Problem	Language	Result	Execution time	Memory
728510		Dead_Inside7	Knapsack (NOI18_knapsack)	C++17	12 / 100	1 ms	340 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;
int main() {
    int cap,n;cin>>cap>>n;
    vector<vector<pair<long long,long long>>> arr(cap+1);
    for(int j=0;j<n;j++){
        int value,weight,amt;
        cin>>value>>weight>>amt;
        arr[weight].push_back({value,amt});
    }
    vector<pair<long long,long long>> knapsack;
    for(int j=1;j<=cap;j++){
        sort(arr[cap].begin(),arr[cap].end());
        reverse(arr[cap].begin(),arr[cap].end());
        vector<long long> subs;
        int i=0;
        while(subs.size()<cap/j&&i<arr[j].size()){
        	while(subs.size()<(cap/j)&&arr[j][i].second>0){
        		subs.push_back(arr[j][i].first);
        		arr[j][i].second--;
        	}
        	i++;
        }
        for(auto it:subs) knapsack.push_back({it,j});
    }
    vector<long long> dp(cap+1);
    dp[0]=0;
    for(int j=0;j<knapsack.size();j++){
    	for(int i=cap;i>=0;i--){
    	if((i-knapsack[j].second)>=0) dp[i]=max(dp[i],dp[i-knapsack[j].second] + knapsack[j].first);
    }
    }
    cout<<dp[cap]<<endl;
    return 0;
}

Compilation message (stderr)

knapsack.cpp: In function 'int main()':
knapsack.cpp:17:26: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   17 |         while(subs.size()<cap/j&&i<arr[j].size()){
      |               ~~~~~~~~~~~^~~~~~
knapsack.cpp:17:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |         while(subs.size()<cap/j&&i<arr[j].size()){
      |                                  ~^~~~~~~~~~~~~~
knapsack.cpp:18:27: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   18 |          while(subs.size()<(cap/j)&&arr[j][i].second>0){
      |                ~~~~~~~~~~~^~~~~~~~
knapsack.cpp:28:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |     for(int j=0;j<knapsack.size();j++){
      |                 ~^~~~~~~~~~~~~~~~

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