Submission #1059397

#	Time	Username	Problem	Language	Result	Execution time	Memory
1059397		theehann	Knapsack (NOI18_knapsack)	C++17	12 / 100	1 ms	348 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ft first
#define se second
#define NAME "A"
#define file freopen(NAME".INP","r",stdin); freopen(NAME".OUT","w",stdout);
#define sdf ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define el cout << "\n"
const int MOD = 1e9 + 7, N = 1e5 + 5;
int n, S;
int32_t main(){
	sdf
	cin >> S >> n;
	map<int, vector<pair<int, int>>> by_weight;
	for(int i = 1;i <= n;++i){
		int v, w, k;
		cin >> v >> w >> k;
		by_weight[w].push_back({v, k});
	}
	int in = 1, ans = 0 ;
	vector<vector<int>> dp(by_weight.size() + 2, vector<int>(S, -1e17));
	dp[0][0] = 0;
	for(auto &[w, a] : by_weight){
		sort(a.begin(), a.end(), greater<pair<int, int>>());
		for(int j = 0;j <= S;++j){
			int c = 0, cur = 0;
			unsigned int id = 0;
			while((c + 1) * w <= j && id < a.size()){
				cur += a[id].ft;
				c++;
				dp[in][j] = max(dp[in][j], dp[in-1][j-c*w] + cur);
				ans = max(ans, dp[in][j]);
				if(c == a[id].se){
					c = 0;
					id++;
				}
			}
		}
		in++;
	}
	cout << ans;
	return 0;
}

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