Submission #470878

#	Time	Username	Problem	Language	Result	Execution time	Memory
470878		huukhang	Knapsack (NOI18_knapsack)	C++17	100 / 100	103 ms	36248 KiB

knapsack

/*
						   Khangnh's code

"You can either experience the pain of discipline or the pain of regret. 
						The choice is yours."
*/

// - Only when necessary :d
// #pragma GCC optimize("Ofast")
// #pragma GCC optimize("unroll-loops")
// #pragma GCC target("avx,avx2,fma")

#include <bits/stdc++.h>
using namespace std;

#define fileopen(a, b) freopen(((string)a + ".inp").c_str(), "r", stdin); freopen(((string)b + ".out").c_str(), "w", stdout);

#define ll long long
#define int long long
#define ld long double
#define fi first
#define se second
#define pb push_back
#define pf push_front
#define pob pop_back
#define pof pop_front
#define eb emplace_back
typedef pair<int, int> pii;

const ll mod = 1e9 + 7;
const ll inf = 1e18;
const double pi = acos(-1);
const double eps = 1e-9;

inline bool ckmax(int &x, const int &y) {return x < y ? x = y, 1 : 0;}

int s, n;
map<int, vector<pii>> a;
int dp[2005][2005];
// dp[i][j]: maximum cost with items of the first i weight types, using j weight

void solve() {
	cin >> s >> n;
	for (int i = 1, v, w, k; i <= n; ++i) {
		cin >> v >> w >> k;
		a[w].pb({v, k});
	}

	for (int i = 0; i <= a.size(); ++i)
		for (int j = 0; j <= s; ++j)
			dp[i][j] = -inf;
	dp[0][0] = 0;

	int idx = 0;
	for (auto &cur : a) {
		int w = cur.fi;
		vector<pii> &item = cur.se;
		sort(item.begin(), item.end(), greater<pii>());

		++idx;
		for (int i = 0; i <= s; ++i) {
			// - We don't take any items of this weight type:
			dp[idx][i] = dp[idx - 1][i];

			// - We take some items of this weight type:
			int copies = 0,		// copies: number of items of this weight type we've used
				type = 0,		// type: current index of this weight type
				used = 0,		// used: number of the current item we've used
				cost = 0;		// cost: current cost
			while ((copies + 1)*w <= i && type < item.size()) {
				++copies;
				cost += item[type].fi;
				if (dp[idx - 1][i - copies*w] != -inf)
					ckmax(dp[idx][i], dp[idx - 1][i - copies*w] + cost);
			
				++used;
				if (used == item[type].se) used = 0, ++type;
			}
		}
	}

	int ans = -inf;
	for (int i = 0; i <= s; ++i) ckmax(ans, dp[idx][i]);
	cout << ans;
}

signed main() {
	#ifdef LOCAL
		fileopen("input", "output");
		auto start = clock();
	#endif
	#ifndef LOCAL
//		fileopen("LAH", "LAH");
	#endif
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int test = 1;
//	cin >> test;
	for (int tc = 1; tc <= test; ++tc) solve();
	#ifdef LOCAL
		auto end = clock();
		cout << "\n\nExecution time : " << double(end - start)/CLOCKS_PER_SEC << "[s]";
	#endif
	return 0;
}

Compilation message (stderr)

knapsack.cpp: In function 'void solve()':
knapsack.cpp:49:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::map<long long int, std::vector<std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |  for (int i = 0; i <= a.size(); ++i)
      |                  ~~^~~~~~~~~~~
knapsack.cpp:70:39: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |    while ((copies + 1)*w <= i && type < item.size()) {
      |                                  ~~~~~^~~~~~~~~~~~~

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