Submission #805828

#	Time	Username	Problem	Language	Result	Execution time	Memory
805828		fnuprince	Knapsack (NOI18_knapsack)	C++17	73 / 100	328 ms	262144 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;
int obj[100000][3] ;
//int dp[2001][100001];
pair<int,int> max(pair<int,int> a, pair<int,int> b) {
	if (a.first > b.first) return a;
	if (b.first > a.first) return b;
	if (a.second < b.second) return a;
	return b;
}
int main() {
	int s, n; cin >> s >> n;
	//vector<array<int,3>> obj(n);
	for (int i = 0; i < n; i++) cin >> obj[i][0] >> obj[i][1] >> obj[i][2];
	vector<vector<pair<int,int>>> dp(n,vector<pair<int,int>>(s+1));
	//for (int i = 0; i < n+1; i++) dp[0][i] = 0;
	/*for (int i = 0; i < s+1; i++) {
		for (int j = 0; j < n; j++) {
			if (i-obj[j][1] >= 0) {
				if (dp[i-obj[j][1]][j+1] < obj[j][2]) {
					if (dp[i][0] < dp[i-obj[j][1]][0]+obj[j][0]) {
						dp[i] = dp[i-obj[j][1]];
						dp[i][0] += obj[j][0];
						dp[i][j+1]++;
					}
					else if (dp[i][0] == dp[i-obj[j][1]][0]+obj[j][0] && dp[i-obj[j][1]][j+1]+1<dp[i][j+1]) {
						dp[i] = dp[i-obj[j][1]];
						dp[i][0] += obj[j][0];
						dp[i][j+1]++;
					}
				}
			}
		}
	}*/
	for (int i = 0; i < n; i++) for (int j = 0; j <= s; j++) dp[i][j] = make_pair(0,0);
	for (int i = 0; i < n; i++) {
		for (int j = 1; j <= s; j++) {
			if (j-obj[i][1] >= 0) {
				for (int k = 1; j-obj[i][1]*k>=0; k++) if (i > 0 && k <= obj[i][2]) dp[i][j] = max(dp[i][j],make_pair(dp[i-1][j-obj[i][1]*k].first+obj[i][0]*k,k));
				if (dp[i][j-obj[i][1]].second < obj[i][2]) dp[i][j] = max(dp[i][j],make_pair(dp[i][j-obj[i][1]].first+obj[i][0],dp[i][j-obj[i][1]].second+1));
			}
			if (i > 0) dp[i][j]= max(dp[i][j],make_pair(dp[i-1][j].first,0));
		}
	}
	int ans = 0;
	for (int j = 0; j < n; j++) for (int i = 0; i <= s; i++) ans = max(dp[j][i].first,ans);
	cout << ans << endl;
}

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