제출 #876000

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
876000		fnuprince	Knapsack (NOI18_knapsack)	C++17	0 / 100	15 ms	24412 KiB

knapsack

#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++;
			}
		}
	}
	cout << dp[s][s] << endl;
}

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