Submission #1241630

#	Time	Username	Problem	Language	Result	Execution time	Memory
1241630		nlsosad	Knapsack (NOI18_knapsack)	C++20	100 / 100	99 ms	34120 KiB

knapsack

#include <bits/stdc++.h>
#define int long long
#define f first
#define s second
using namespace std;
vector<pair<int, int>> a[2001];
int dp[2001][2001];
signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n, s;
	cin >> s >> n;
	for (int i = 1;i<=n;++i){
		int v, w, k;
		cin >> v >> w >> k;
		a[w].push_back({v, k});
	}
	for (int i = 1;i<=s;++i){
		sort(a[i].begin(),a[i].end(), [](pair<int, int>p, pair<int, int> q){
			return p.f > q.f;
		});
	}
	for (int i = 1;i<=s;++i){
		for (int j = 1;j<=s;++j){
			dp[i][j] = max(dp[i][j], dp[i][j-1]);
			int tmp = i-j;
			int dem = 1;
			int tro = -1;
			int pf = 0;
			int pre = 0;
			while(tmp >= 0 and tro < (int)a[j].size()){
				// cout << tmp << ' ' << tro << '\n';
				// cout << "NGU\n";
				if(dem>pf){
					tro++;
					if(tro==a[j].size())break;
					pf+=a[j][tro].s;
				}
				pre += a[j][tro].f;
				dp[i][j] = max(dp[i][j], dp[tmp][j-1] + pre);
				tmp-=j;
				dem++;
			}
		}
	}
	/*for (int i = 1;i<=s;++i){
		for (int j = 1;j<=s;++j){
			cout << dp[i][j] << ' ';
		}
		cout << '\n';
	}*/
	cout << dp[s][s];
}

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