Submission #988234

#	Time	Username	Problem	Language	Result	Execution time	Memory
988234		vjudge1	Knapsack (NOI18_knapsack)	C++17	0 / 100	1 ms	344 KiB

knapsack

#include <bits/stdc++.h>

using namespace std;

void solve(){
    long long s,n;cin>>s,n;
    vector<vector<pair<long long,long long>>> w(s+5);
    for(long long  i=0;i<n;i++){
        long long v,we,k;cin>>v>>we>>k;
        w[we].push_back({v,k});
    }
    vector<pair<long long,long long>> v;
    for(long long i=0;i<s+2;i++){
        if(w[i].empty()) continue;
        sort(w[i].begin(),w[i].end());
        long long ct=(s+i-1)/i;
        for(;w[i].size() && ct--;){
            w[i].back().second--;
            v.push_back({i,w[i].back().first});
            if(!w[i].back().second) w[i].pop_back();
        }
    }
    vector<long long> dp(s+10,0);
    dp[0]=0;
    for(long long i=0;i<v.size();i++){
        for(long long j=s+5;j>=v[i].first;j--){
            dp[i]=max(dp[j],dp[j-v[i].first]+v[i].second);
        }
    }
    long long res=0;
    for(long long i=0;i<s+1;i++) res=max(res,dp[i]);cout<<res<<"\n";
}

int main(){
//    fastio
    solve();
}

Compilation message (stderr)

knapsack.cpp: In function 'void solve()':
knapsack.cpp:7:27: warning: right operand of comma operator has no effect [-Wunused-value]
    7 |     long long s,n;cin>>s,n;
      |                           ^
knapsack.cpp:26: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]
   26 |     for(long long i=0;i<v.size();i++){
      |                       ~^~~~~~~~~
knapsack.cpp:32:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   32 |     for(long long i=0;i<s+1;i++) res=max(res,dp[i]);cout<<res<<"\n";
      |     ^~~
knapsack.cpp:32:53: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   32 |     for(long long i=0;i<s+1;i++) res=max(res,dp[i]);cout<<res<<"\n";
      |                                                     ^~~~
knapsack.cpp:9:25: warning: 'n' may be used uninitialized in this function [-Wmaybe-uninitialized]
    9 |     for(long long  i=0;i<n;i++){
      |                        ~^~

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