Submission #998556

#	Time	Username	Problem	Language	Result	Execution time	Memory
998556		vjudge1	Knapsack (NOI18_knapsack)	C++17	100 / 100	246 ms	239960 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;
//#define int long long 

#define fi first
#define se second
#define pii pair<int,int>
const int NN = 1e5+5;
vector<int> a[3000]; 
int dp[30005][2005];
int v[NN] , w[NN] , k[NN] ;
struct ha{
	int v , w ;
};
vector<ha> lis;
bool ss(int a , int b){
	return v[a] > v[b];
} 
int di(int vt , int cl){
	if(vt<0) return 0;
	if(dp[vt][cl]!= -1) return dp[vt][cl];
	dp[vt][cl] = di(vt-1 , cl);
	if(cl >= lis[vt].w){
		dp[vt][cl] = max(dp[vt][cl] ,di(vt-1 , cl-lis[vt].w)+lis[vt].v);
	}
	return dp[vt][cl];
}

signed main(){
//		int sum = 0 ; 
//	for(int i = 1  ;i <= 2000 ; i++){
//		sum+=2000/i;
//	}
//	cout << sum <<'\n';
	
	
	
	
//	freopen("connect.in", "r", stdin);
//	freopen("connect.out", "w", stdout);
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	
	int n , s;
	cin >> s >> n; 
	for(int i =1  ;i <= n  ;i++){
		cin >> v[i] >> w[i] >> k[i] ; 
		a[w[i]].push_back(i);
	}

	for(int i = 1 ;i <= s ; i++){
		sort(a[i].begin(),a[i].end() , ss);
		int sl = 0 ; 
		int tg = s/i , x;
		for(int l : a[i]){
			if(sl +k[l]<= tg){
				sl += k[l];
				x = k[l];
			}else{
				x = tg-sl;
				sl = tg+1;
			}
				
			for(int j = 0 ; j <= 30 ; j ++){
				int op = 1<<j;
				if(x>= op){
					x-=op;
					lis.push_back({v[l]*op ,w[l]*op});
				}
			}
			if(x != 0){
				lis.push_back({v[l]*x ,w[l]*x});
			}
			if(sl > tg) break;
		}
	}
//	for(ha v : lis) cout << v.v <<" "<< v.w<<'\n;
	memset(dp , -1 , sizeof(dp));
	n = lis.size()-1;
	cout << di(n , s);
} 

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