Submission #728538

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

knapsack

#include <bits/stdc++.h>
using namespace std;
int main() {
    long long cap,n;cin>>cap>>n;
    vector<vector<pair<long long,long long>>> arr(cap+1);
    for(long long j=0;j<n;j++){
        long long value,weight,amt;
        cin>>value>>weight>>amt;
        arr[weight].push_back({value,amt});
    }
    vector<pair<long long,long long>> knapsack;
    for(long long j=1;j<=cap;j++){
        sort(arr[cap].begin(),arr[cap].end());
        reverse(arr[cap].begin(),arr[cap].end());
        vector<long long> subs;subs.clear();
        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(long long j=0;j<knapsack.size();j++){
    	for(long long 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:27: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   17 |         while((subs.size()<=(cap/j))&&(i<arr[j].size())){
      |                ~~~~~~~~~~~^~~~~~~~~
knapsack.cpp:17:41: 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:28: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   18 |          while((subs.size()<=(cap/j))&&(arr[j][i].second>0)){
      |                 ~~~~~~~~~~~^~~~~~~~~
knapsack.cpp:28:24: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |     for(long long 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