Submission #898789

#	Time	Username	Problem	Language	Result	Execution time	Memory
898789		Amaarsaa	Knapsack (NOI18_knapsack)	C++14	100 / 100	59 ms	5464 KiB

knapsack

#include<bits/stdc++.h>

using namespace std;
using ll = int;
const int N = 1e5 + 2;
ll weight[N], CanAdd[N], price[N], Left[N];
vector < pair < ll, ll > > W[2002];
ll dp[N];
int main() {
//	freopen("moocast.in", "r", stdin);
//	freopen("moocast.out", "w", stdout);
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	ll i, ans, j, r, last, now, n, k, p;

	cin >> k >> n;
	
	
	for (i = 1; i <= n; i ++) {
		cin >> price[i] >> weight[i] >> Left[i];
		if ( weight[i] <= k && Left[i] > 0) W[weight[i]].push_back({price[i], Left[i]});
	}
	vector < pair < ll, ll > > v;
	for (i = 1; i <= k; i ++) {
		sort(W[i].begin(), W[i].end(), greater<pair < ll, ll > >());
		r = k/i;
		p = 0;
		while ( r > 0 && p < W[i].size()) {
			v.push_back({i, W[i][p].first});
			if ( W[i][p].second == 0) p ++;
			else {
				W[i][p].second --;
				if ( W[i][p].second == 0) p ++;
			}
			r --;
		}
	}
	ans = 0;
	memset(dp, -0x3f, sizeof dp);
	dp[0] = 0;
	for (i = 0; i < v.size(); i ++) {
		for (j = k; j >= v[i].first; j --) {
			dp[j] = max(dp[j], dp[j - v[i].first] + v[i].second); 
			ans = max(ans, dp[j]);
		}
	}
	cout << ans << endl;
	
		
}

Compilation message (stderr)

knapsack.cpp: In function 'int main()':
knapsack.cpp:28:22: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |   while ( r > 0 && p < W[i].size()) {
      |                    ~~^~~~~~~~~~~~~
knapsack.cpp:41:16: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |  for (i = 0; i < v.size(); i ++) {
      |              ~~^~~~~~~~~~
knapsack.cpp:14:19: warning: unused variable 'last' [-Wunused-variable]
   14 |  ll i, ans, j, r, last, now, n, k, p;
      |                   ^~~~
knapsack.cpp:14:25: warning: unused variable 'now' [-Wunused-variable]
   14 |  ll i, ans, j, r, last, now, n, k, p;
      |                         ^~~

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