Submission #1137264

#	Time	Username	Problem	Language	Result	Execution time	Memory
1137264		gadun	Knapsack (NOI18_knapsack)	C++20	73 / 100	461 ms	327680 KiB

knapsack

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;

using namespace std;
using ll = long long;
const int MOD = 13371337;
const int INF = INT_MAX;
const int MAXN = 1e9;
#define ci pair<char,ll>
#define ii pair<ll,ll>
#define iii pair<ll, pair<ll, ll>>
#define fi first
#define mp(x,y) make_pair(x, y)
#define se second
#define show(x) cerr << #x << " is " << x << endl;
#define f0r(n) for(int i = 0; i < n; i++)
//#define int long long

int32_t main(){
  ios::sync_with_stdio(0); cin.tie(0);
	int s, n;
	cin >> s >> n;
	vector<vector<int>> v(s+1);
	for (int i =1 ; i <= n; i++){
		int val, weight, amt;
		cin >> val >> weight >> amt;
		for (int j = 0; j < min(s/weight,amt); j++){
			v[weight].push_back(val);
		}
	}
	for (int i = 1; i <= s; i++){
		sort(v[i].begin(), v[i].end(), greater<int>());
	}
	int dp[s+1];
	memset(dp, 0, sizeof dp);

	for (int i = 1; i <= s; i++){
		for (int amt = 0; amt < min((int)v[i].size(), s/i); amt++){
			for (int j = s; j >= 1; j--){
				if (j >= i) dp[j] = max(dp[j], dp[j-i] + v[i][amt]);
				dp[j] =max(dp[j], dp[j-1]);
			}
		}
	}
	
	
	int ans = -1e9;
	for (int j = 0; j <= s;j ++){
		ans = max(ans, dp[j]);
	}
	cout << ans << endl;
}

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