Submission #843890

#	Time	Username	Problem	Language	Result	Execution time	Memory
843890		Ablabla	Knapsack (NOI18_knapsack)	C++11	100 / 100	116 ms	36436 KiB

knapsack

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pii;

int main(){
	ll s, n;
	cin >> s >> n;

	map<ll, vector<pii>> sorban;
	for(ll t = 0; t < n; t++) {
		ll ertek;
		ll suly;
		ll db;
		cin >> ertek >> suly >> db;
		if(suly <= s && db > 0) {
			sorban[suly].push_back({ertek, db});
		}
	}

	vector<vector<ll>> dp(sorban.size() + 1, vector<ll>(s + 1, INT32_MIN));
	dp[0][0] = 0;
	ll ind = 1;
	for(auto &[ertek, szam] : sorban) {
		sort(szam.begin(), szam.end(), greater<pii>());
		for(ll i = 0; i <= s; i++) {
			dp[ind][i] = dp[ind - 1][i];
			ll felhasznalt = 0;
			ll tipus = 0;
			ll marFelhasznalt = 0;
			ll plusz = 0;

			while((felhasznalt + 1) * ertek <= i && tipus < szam.size()) {
				felhasznalt++;
				plusz += szam[tipus].first;
				if(dp[ind - 1][i - felhasznalt * ertek] != INT32_MIN) {
					dp[ind][i] = max(dp[ind][i], dp[ind - 1][i - felhasznalt * ertek] + plusz);
				}

				marFelhasznalt++;
				if(marFelhasznalt == szam[tipus].second) {
					marFelhasznalt = 0;
					tipus++;
				}
			}
		}
		ind++;
	}

	cout << *max_element(dp.back().begin(), dp.back().end()) << endl;
}

Compilation message (stderr)

knapsack.cpp: In function 'int main()':
knapsack.cpp:26:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   26 |  for(auto &[ertek, szam] : sorban) {
      |            ^
knapsack.cpp:35:50: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |    while((felhasznalt + 1) * ertek <= i && tipus < szam.size()) {
      |                                            ~~~~~~^~~~~~~~~~~~~

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