Submission #771145

#	Time	Username	Problem	Language	Result	Execution time	Memory
771145		8pete8	Knapsack (NOI18_knapsack)	C++14	100 / 100	76 ms	36360 KiB

knapsack

#include<bits/stdc++.h>
using namespace std;
#define f first
#define ll long long
#define endl "\n"
#define s second
#define pii pair<int,int>
#define pppiiii pair<pii,pii>
#define ppii pair<pii,int>
#define pll pair<ll,ll>
#define ppll pair<ll,pair<ll,ll>>
#define pbb pair<bool,bool>
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);
const int mxn=1e5+1;
#define int long long
int dp[mxn+10][2002];
bool cmp(pii a,pii b){return a.f>b.f;}
int32_t main(){
    fastio
    int s,n;cin>>s>>n;
    map<int,vector<pii>>mp;
    for(int i=1;i<=n;i++){
        int v,w,k;cin>>v>>w>>k;
        mp[w].push_back({v,k});
    }
    //val, weight, how many
    int cnt=1,ans=0;
    for(auto i:mp){
        sort(i.s.begin(),i.s.end(),cmp);
        for(int j=1;j<=s;j++){
            dp[cnt][j]=dp[cnt-1][j];
            int cur=1,curi=0,cost=0,cnt2=1;
            while(curi<i.s.size()&&j-(cnt2*i.f)>=0){
                cost+=i.s[curi].f;
                dp[cnt][j]=max(dp[cnt-1][j-(cnt2*i.f)]+cost,dp[cnt][j]);
                if(cur==i.s[curi].s){
                    cur=1;
                    curi++;
                }
                else cur++;
                cnt2++;
            }
            ans=max(ans,dp[cnt][j]);
        }
        cnt++;
    }
    cout<<ans<<'\n';
}

Compilation message (stderr)

knapsack.cpp: In function 'int32_t main()':
knapsack.cpp:33:23: 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]
   33 |             while(curi<i.s.size()&&j-(cnt2*i.f)>=0){
      |                   ~~~~^~~~~~~~~~~

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