Submission #1256181

#	Time	Username	Problem	Language	Result	Execution time	Memory
1256181		namhh	Knapsack (NOI18_knapsack)	C++20	100 / 100	39 ms	7496 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
#define fi first
#define se second
const int N = 1e5+5;
int n,w,dp[N],old[N];
vector<pii>adj[N];
vector<int>chon[N];
signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> w >> n;
	for(int i = 1; i <= n; i++){
		int u,v,c;
		cin >> u >> v >> c;
		adj[v].push_back({u,c});
	}
	for(int i = 1; i <= w; i++){
		int cnt = 0;
	    sort(adj[i].begin(),adj[i].end());
	    reverse(adj[i].begin(),adj[i].end());
	    for(auto it: adj[i]){
	    	if(cnt+it.se <= w/i){
	    		for(int j = 1; j <= it.se; j++) chon[i].push_back(it.fi);
	    		cnt += it.se;
			}
			else{
				for(int j = 1; j <= w/i-cnt; j++) chon[i].push_back(it.fi);
				break;
			}
		}
	}
	for(int i = 1; i <= w; i++){
		for(int j = 1; j <= w; j++) old[j] = dp[j];
		for(int j = 0; j < chon[i].size(); j++){
			for(int k = w; k >= i; k--) dp[k] = max(dp[k],dp[k-i]+chon[i][j]);
		}
	}
	int ans = 0;
	for(int i = 1; i <= w; i++) ans = max(ans,dp[i]);
	cout << ans;
}

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