Submission #1314346

#	Time	Username	Problem	Language	Result	Execution time	Memory
1314346		kevin264	Knapsack (NOI18_knapsack)	C++20	100 / 100	65 ms	65664 KiB

knapsack

#include <bits/stdc++.h> 

using namespace std;
#define int long long
#define endl '\n'
#define ff first
#define ss second
#define m_p make_pair
#define INF LLONG_MAX
using vi=vector<int>;
using vvi=vector<vi>;
using pii=pair<int,int>;
using vpii=vector<pii>;

int32_t main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr); 
int s,n;
cin>>s>>n;
vector<vpii> v(s+1);
while(n--){
    int value,w,k;
    cin>>value>>w>>k;
    v[w].push_back({value,k}); 
}
vvi pref(s+1,vi(s+1,-1));
for(auto i=0;i<=s;i++) {
    vpii& c=v[i];
    if(c.empty()) continue;
    sort(c.begin(),c.end(),greater<pii>()); 
    int it=0;
    int sum=c[0].ss;
    int ant=0; 
    while(ant<=s){
      pref[i][ant]=it;
      ant++;
      if(ant==sum){
       int sz=c.size()-1;
       if(it==sz) break;
       it++;
       sum+=c[it].ss;
    }
    } 
}
vi dp(s+1,-1); 
dp[0]=0;
vector<pair<pair<int,int>,vi> >  f(s+1,{{-1,-1},vi(s+1,0)}); 
f[0].ff={0,0};
for(int i=0;i<=s;i++){
if(dp[i]==-1) continue; 
f[i].ss[f[i].ff.ss]=1;
for(int j=0;j<=s-i;j++){
    if(v[j].empty()) continue;
    f[i].ss[j]+=f[f[i].ff.ff].ss[j]; 
    int it=pref[j][f[i].ss[j]];
    if(it==-1) continue; 
    int s=i+j;
    if(dp[s]<dp[i]+v[j][it].ff){
        dp[s]=dp[i]+v[j][it].ff;
        f[s].ff={i,j};
    }
}
}
int ans=0;
for(auto i : dp) ans=max(ans,i);
cout<<ans<<endl;
return 0;
}

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