Submission #967243

#	Time	Username	Problem	Language	Result	Execution time	Memory
967243		SmuggingSpun	Knapsack (NOI18_knapsack)	C++14	100 / 100	44 ms	4180 KiB

knapsack

#include<bits/stdc++.h>
#define taskname "knapsack"
using namespace std;
template<class T>void maximize(T& a, T b){
	if(a < b){
		a = b;
	}
}
const int lim = 2e3 + 1;
int cnt[lim], dp[lim];
vector<int>a[lim];
int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	if(fopen(taskname".inp", "r")){
		freopen(taskname".inp", "r", stdin);
	}
	memset(cnt, 0, sizeof(cnt));
	int S, n;
	cin >> S >> n;
	vector<int>v(n), w(n), k(n);
	for(int i = 0; i < n; i++){
		cin >> v[i] >> w[i] >> k[i]; 
	}
	vector<int>p(n);
	iota(p.begin(), p.end(), 0);
	sort(p.begin(), p.end(), [&] (int i, int j) -> bool{
		return v[i] > v[j];
	});
	for(int& i : p){
		int max_size = S / w[i];
		while(a[w[i]].size() < max_size && k[i] > 0){
			a[w[i]].emplace_back(v[i]);
			k[i]--;
		}
	}
	memset(dp, 0, sizeof(dp));
	for(int i = 1; i <= S; i++){
		for(int j = S; j >= i; j--){
			for(int k = 0, value = 0; k < a[i].size() && i * (k + 1) <= j; k++){
				maximize(dp[j], dp[j - i * (k + 1)] + (value += a[i][k]));
			}
		}
	}
	cout << dp[S];
}

Compilation message (stderr)

knapsack.cpp: In function 'int main()':
knapsack.cpp:31:24: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   31 |   while(a[w[i]].size() < max_size && k[i] > 0){
      |         ~~~~~~~~~~~~~~~^~~~~~~~~~
knapsack.cpp:39:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |    for(int k = 0, value = 0; k < a[i].size() && i * (k + 1) <= j; k++){
      |                              ~~^~~~~~~~~~~~~
knapsack.cpp:15:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |   freopen(taskname".inp", "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

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