Submission #999528

#	Time	Username	Problem	Language	Result	Execution time	Memory
999528		ef10	Knapsack (NOI18_knapsack)	C++17	100 / 100	105 ms	36176 KiB

knapsack

// Source: https://usaco.guide/general/io

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

#define LL long long

int main() {
	LL S, N; cin >> S >> N;
	tuple<LL, LL, LL> A[N+1]; memset(A,0,sizeof(A));
	for (LL i = 1; i <= N; i++) {
		LL v,w,k;
		cin >> v >> w >> k;
		A[i] = make_tuple(w,v,k);
	}
	sort(A+1,A+N+1,greater<tuple<LL,LL,LL> >());
	LL D[S+1][S+1]; memset(D,0,sizeof(D));
	LL ind = 1;
	while (ind <= N) {
		LL s = get<0>(A[ind]);
		LL id = 1;
		while (ind <= N && get<0>(A[ind]) == s)  {
			for (LL j = 0; j < get<2>(A[ind]) && id <= S; j++) {
				D[s][id++] = get<1>(A[ind]);
			}
			ind++;
			if (id > S) break;
		}
		while (ind <= N && get<0>(A[ind]) == s) ind++;
	}
	LL dp[2][S+1];
	for (LL i = 0; i < 2; i++) {
		dp[i][0] = 0;
		for (LL j = 1; j <= S; j++) {
			dp[i][j] = -1;
		}
	}
	for (LL i = 1; i <= S; i++) {
		LL ind = i%2;
		LL oi = (i+1)%2;
		for (LL j = S; j >= 0; j--) {
			dp[ind][j] = dp[oi][j];
			if (dp[ind][j] < 0) continue;
			for (LL w = i,id=1,v=D[i][id],V=v; w+j <= S && v > 0 && id <= S; w+=i,id++,v=D[i][id],V+=v) {
				dp[ind][w+j] = max(dp[ind][w+j], dp[ind][j]+V);
			}
		}
	}
	LL res = 0;
	for (LL i = 1; i <= S; i++) {
		res = max(res, dp[S%2][i]);
	}
	cout << res << endl;
}

Compilation message (stderr)

knapsack.cpp: In function 'int main()':
knapsack.cpp:10:48: warning: 'void* memset(void*, int, size_t)' clearing an object of type 'class std::tuple<long long int, long long int, long long int>' with no trivial copy-assignment; use assignment instead [-Wclass-memaccess]
   10 |  tuple<LL, LL, LL> A[N+1]; memset(A,0,sizeof(A));
      |                                                ^
In file included from /usr/include/c++/10/functional:54,
                 from /usr/include/c++/10/pstl/glue_algorithm_defs.h:13,
                 from /usr/include/c++/10/algorithm:74,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from knapsack.cpp:3:
/usr/include/c++/10/tuple:516:11: note: 'class std::tuple<long long int, long long int, long long int>' declared here
  516 |     class tuple : public _Tuple_impl<0, _Elements...>
      |           ^~~~~

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