Submission #823908

#	Time	Username	Problem	Language	Result	Execution time	Memory
823908		Anthony_Liu	Knapsack (NOI18_knapsack)	C++11	100 / 100	125 ms	35056 KiB

knapsack

#include<bits/stdc++.h>
using namespace std;
//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx2")
//#pragma GCC optimization ("unroll-loops")
#define f first
#define s second
#define ll long long
#define pb push_back 
#define pi pair <int,int>
#define vi vector <int>
#define size(x) (int)(x).size()
#define all(x) x.begin(), x.end()
void setIO(string name = "") {
	cin.tie(0)->sync_with_stdio(0);
	if (size(name)) {
		freopen((name + ".in").c_str(), "r", stdin);
		freopen((name + ".out").c_str(), "w", stdout);
	}
}

int W, N;
vector <vector<pi>> items;
vector <vector<ll>> dp;

int main()
{
	setIO();
	cin >> W >> N;
	items.resize(W + 1);
	dp.resize(W + 1, vector<ll>(W + 1, 0));
	
	for (int i = 1; i <= N; i++) {
		int v, w, k;
		cin >> v >> w >> k;
		items[w].pb({-v, k});
	}
	for (int i = 1; i <= W; i++) {
		if (size(items[i]))
			sort(all(items[i]));
	}
	
	ll ans = 0;
	//dp[2][1] = 2 should be 3
	for (int i = 1; i <= W; i++)
	{
		for (int j = 1; j <= W; j++) 
		{
			dp[i][j] = dp[i][j - 1];//0
			if (size(items[j]) == 0) continue;
			
			ll cur = 0;
			int index = i;
			
			for (auto item : items[j]) {
				bool br = false;
				for (int it = 1; it <= item.s; it++) {
					cur -= item.f;
					index -= j;
					if (index < 0) {
						br = 1;
						break;
					}
					dp[i][j] = max(dp[i][j], dp[index][j - 1] + cur);
				}
				if (br) break;
			}
			//cout << i << '/' << j << '/' << dp[i][j] << ' ';
			ans = max(ans, dp[i][j]);
		}
		//cout << '\n';
	}
	cout << ans << '\n';
	return 0;
}

Compilation message (stderr)

knapsack.cpp: In function 'void setIO(std::string)':
knapsack.cpp:17:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |   freopen((name + ".in").c_str(), "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
knapsack.cpp:18:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |   freopen((name + ".out").c_str(), "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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