Submission #795839

#	Time	Username	Problem	Language	Result	Execution time	Memory
795839		KLPP	Knapsack (NOI18_knapsack)	C++14	100 / 100	232 ms	126240 KiB

knapsack

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
using namespace std;
using namespace __gnu_pbds;
typedef long long int lld;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
#define rep(i,a,b) for(int i=a;i<b;i++)
#define trav(a,v) for(auto a:v)
const lld MOD=1e9+7;
const int MAX=3'000'000;
lld fact[MAX];
lld inv[MAX];
lld ModPow(lld base, lld exp){
	if(exp==0)return 1;
	if(exp%2==1)return (base*ModPow(base,exp-1))%MOD;
	lld a=ModPow(base,exp/2);
	return (a*a)%MOD;
}
lld comb(int a, int b){
	if(b<0 || b>a)return 0;
	lld ans=fact[a];
	ans*=inv[b];
	ans%=MOD;
	ans*=inv[a-b];
	ans%=MOD;
	return ans;
}
void solve(){
	int s,n;
	cin>>s>>n;
	vector<pair<lld,lld> >V;
	vector<vector<lld> >best(s+1);
	rep(i,0,n){
		lld v,w,k;
		cin>>v>>w>>k;
		while(k>0){
			int res=k%2;
			if(res==0)res=2;
			rep(j,0,res){
				V.push_back({v,w});
			}
			k-=res;
			k/=2;
			v*=2;
			w*=2;
		}
	}
	trav(a,V){
		if(a.second<=s){
			best[a.second].push_back(a.first);
		}
	}
	rep(i,0,s+1){
		sort(best[i].begin(),best[i].end());
		reverse(best[i].begin(),best[i].end());
		while((lld)(best[i].size())*(lld)i>s){
			best[i].pop_back();
		}
	}
	vector<lld> DP(s+1,0);
	rep(w,0,s+1){
		trav(v,best[w]){
			if(w<=s){
				for(lld i=s;i-w>=0;i--){
					DP[i]=max(DP[i],DP[i-w]+v);
				}
			}
		}
	}
	cout<<DP[s]<<"\n";
}

int main(){
	fact[0]=1;
	rep(i,1,MAX)fact[i]=(i*fact[i-1])%MOD;
	inv[MAX-1]=ModPow(fact[MAX-1],MOD-2);
	for(int i=MAX-2;i>-1;i--)inv[i]=((i+1)*inv[i+1])%MOD;
	ios::sync_with_stdio(0);
	cin.tie(0);
	int tt=1;
	while(tt--){
		solve();
	}
}

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