Submission #860758

#	Time	Username	Problem	Language	Result	Execution time	Memory
860758		dosts	Knapsack (NOI18_knapsack)	C++17	100 / 100	80 ms	65876 KiB

knapsack

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
#define sp << " " << 
#define int long long
#define vi vector<int>
#define pb push_back
#define F(xxx,yyy) for (int xxx=1;xxx<=yyy;xxx++)
#define pii pair<int,int>
#define ordered_set tree<pii, null_type, less<pii>, rb_tree_tag, tree_order_statistics_node_update>
const int MOD = 1e9+9;

int add(int x,int y) {return ((x%MOD)+(y%MOD))%MOD;}


void solve() { 
	int n,s;
	cin >> s >> n;
	priority_queue<pii> items[s+1];
	vi sz(s+1,0);
	F(i,n) {
		int v,w,q;
		cin >> v >> w >> q;
		items[w].push({v,q});
		sz[w]+=q;
	}
	vector<vi> dp(s+1,vi(s+1,-2e18));
	vector<vi> c(s+1,vi(s+1,0));
	for (int i=1;i<=s;i++) {
		int got = 0;
		int taken = 0;
		c[i][0] = 0;
		for (int j=1;i*j<=s;j++) {
			if (items[i].empty()) break;
			got+=items[i].top().first;
			taken++;
			c[i][j] = got;
			if (taken == items[i].top().second) {
				taken = 0;
				items[i].pop();
			}
		}
	}
	dp[0][0] = 0;
	F(i,s) {
		for (int j=0;j<=s;j++) {
			for (int take = 0;take<=sz[i] && take*i+j<=s;take++) {
				dp[i][j+take*i] = max(dp[i][j+take*i],dp[i-1][j]+c[i][take]);
			}
		}
	}
	cout << *max_element(dp[s].begin(),dp[s].end()) << endl;
}       
                 
                 
                                
signed main() { 
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t = 1;
    //cin >> t; 
    while (t --> 0) solve();
}

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