Submission #876001

#	Time	Username	Problem	Language	Result	Execution time	Memory
876001		fnuprince	Knapsack (NOI18_knapsack)	C++17	100 / 100	136 ms	66676 KiB

knapsack

// Source: https://usaco.guide/general/io

#include <bits/stdc++.h>
using namespace std;
bool cmppairpair(pair<int,pair<int,int>> a, pair<int,pair<int,int>> b) {
	return a.first > b.first;
}
int main() {
	int s,n; cin >> s >> n;
	vector<pair<int,pair<int,int>>> items(n); for (int i = 0; i < n; i++) cin >> items[i].first >> items[i].second.first >> items[i].second.second;
	sort(items.begin(),items.end(),cmppairpair);
	vector<vector<int64_t>> fir(s+1,vector<int64_t>(s+1,0));
	vector<int> currpointers(s+1,0);
	for (int i = 0; i < n; i++) {
		pair<int,pair<int,int>> curr = items[i];
		if (curr.second.first <= s) {
			for (int j = 0; j < curr.second.second; j++) {
				if (currpointers[curr.second.first] == s) break;
				fir[curr.second.first][currpointers[curr.second.first]+1] = curr.first+fir[curr.second.first][currpointers[curr.second.first]];
				currpointers[curr.second.first]++;
			}
		}
	}
	vector<vector<int64_t>> dp(s+1,vector<int64_t>(s+1,0));
	for (int i = 1; i <= s; i++) {
		for (int j = 1; j <= s; j++) {
			dp[i][j] = max(dp[i][j-1],dp[i-1][j]);
			int k = 1;
			while (i*k <= j && fir[i][k] != 0) {
				dp[i][j] = max(dp[i][j],dp[i-1][j-i*k]+fir[i][k]);
				k++;
			}
		}
	}
	/*for (auto i : dp) {
		for (int64_t j : i) cout << j << " ";
		cout << endl;
	}
	cout<<endl;
	for (auto i : fir) {
		for (int64_t j : i) cout << j << " ";
		cout << endl;
	}*/
	cout << dp[s][s] << endl;
}

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