Submission #471118

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
471118	2021-09-07T09:11:32 Z	avijeet_03	Knapsack (NOI18_knapsack)	C++17	49 / 100	1000 ms	2048 KB

knapsack

#include "bits/stdc++.h"
using namespace std;
#define int long long
const int mod = 1e9 + 7;

const int N = 105;
int value[N], weight[N], amount[N];

int dp[N][2005];

int calc(int i, int cap) {
	if (i == 0 or cap == 0)
		return 0;

	int &res = dp[i][cap];
	if (res != -1) return res;

	int temp = 0;
	for (int k = 0; k <= amount[i]; k++)
		if (k * weight[i] <= cap)
			temp = max(temp, k * value[i] + calc(i - 1, cap - k * weight[i]));

	return res = temp;
}

void test_case() {
	int cap, n;
	cin >> cap >> n;

	for (int i = 1; i <= n; i++)
		cin >> value[i] >> weight[i] >> amount[i];

	memset(dp, -1, sizeof(dp));
	int res = calc(n, cap);
	cout << res << "\n";
}

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	test_case();
	return 0;
}

Subtask #1

12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	1868 KB	Output is correct
2	Correct	28 ms	1860 KB	Output is correct
3	Correct	1 ms	1868 KB	Output is correct
4	Correct	142 ms	1940 KB	Output is correct

Subtask #2

17.0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	1868 KB	Output is correct
2	Correct	1 ms	1868 KB	Output is correct
3	Correct	1 ms	1868 KB	Output is correct
4	Correct	1 ms	1868 KB	Output is correct
5	Correct	1 ms	1868 KB	Output is correct
6	Correct	3 ms	1868 KB	Output is correct
7	Correct	4 ms	1868 KB	Output is correct
8	Correct	3 ms	1852 KB	Output is correct
9	Correct	4 ms	1860 KB	Output is correct
10	Correct	5 ms	1868 KB	Output is correct

Subtask #3

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	1868 KB	Output is correct
2	Correct	1 ms	1868 KB	Output is correct
3	Correct	1 ms	1868 KB	Output is correct
4	Correct	1 ms	1868 KB	Output is correct
5	Correct	1 ms	1868 KB	Output is correct
6	Correct	3 ms	1868 KB	Output is correct
7	Correct	4 ms	1868 KB	Output is correct
8	Correct	3 ms	1852 KB	Output is correct
9	Correct	4 ms	1860 KB	Output is correct
10	Correct	5 ms	1868 KB	Output is correct
11	Correct	1 ms	1868 KB	Output is correct
12	Correct	6 ms	1868 KB	Output is correct
13	Correct	2 ms	2048 KB	Output is correct
14	Correct	1 ms	1868 KB	Output is correct
15	Correct	1 ms	1868 KB	Output is correct
16	Correct	6 ms	1868 KB	Output is correct
17	Correct	3 ms	1868 KB	Output is correct
18	Correct	4 ms	1868 KB	Output is correct
19	Correct	5 ms	1868 KB	Output is correct
20	Correct	4 ms	1868 KB	Output is correct

Subtask #4

0 / 24.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	1868 KB	Output is correct
2	Correct	28 ms	1860 KB	Output is correct
3	Correct	1 ms	1868 KB	Output is correct
4	Correct	142 ms	1940 KB	Output is correct
5	Correct	1 ms	1868 KB	Output is correct
6	Correct	1 ms	1868 KB	Output is correct
7	Correct	1 ms	1868 KB	Output is correct
8	Correct	1 ms	1868 KB	Output is correct
9	Correct	1 ms	1868 KB	Output is correct
10	Correct	3 ms	1868 KB	Output is correct
11	Correct	4 ms	1868 KB	Output is correct
12	Correct	3 ms	1852 KB	Output is correct
13	Correct	4 ms	1860 KB	Output is correct
14	Correct	5 ms	1868 KB	Output is correct
15	Correct	1 ms	1868 KB	Output is correct
16	Correct	6 ms	1868 KB	Output is correct
17	Correct	2 ms	2048 KB	Output is correct
18	Correct	1 ms	1868 KB	Output is correct
19	Correct	1 ms	1868 KB	Output is correct
20	Correct	6 ms	1868 KB	Output is correct
21	Correct	3 ms	1868 KB	Output is correct
22	Correct	4 ms	1868 KB	Output is correct
23	Correct	5 ms	1868 KB	Output is correct
24	Correct	4 ms	1868 KB	Output is correct
25	Correct	2 ms	1868 KB	Output is correct
26	Correct	747 ms	1948 KB	Output is correct
27	Correct	1 ms	1868 KB	Output is correct
28	Correct	2 ms	1856 KB	Output is correct
29	Execution timed out	1092 ms	1868 KB	Time limit exceeded
30	Halted	0 ms	0 KB	-

Subtask #5

0 / 27.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	1868 KB	Output is correct
2	Correct	28 ms	1860 KB	Output is correct
3	Correct	1 ms	1868 KB	Output is correct
4	Correct	142 ms	1940 KB	Output is correct
5	Correct	1 ms	1868 KB	Output is correct
6	Correct	1 ms	1868 KB	Output is correct
7	Correct	1 ms	1868 KB	Output is correct
8	Correct	1 ms	1868 KB	Output is correct
9	Correct	1 ms	1868 KB	Output is correct
10	Correct	3 ms	1868 KB	Output is correct
11	Correct	4 ms	1868 KB	Output is correct
12	Correct	3 ms	1852 KB	Output is correct
13	Correct	4 ms	1860 KB	Output is correct
14	Correct	5 ms	1868 KB	Output is correct
15	Correct	1 ms	1868 KB	Output is correct
16	Correct	6 ms	1868 KB	Output is correct
17	Correct	2 ms	2048 KB	Output is correct
18	Correct	1 ms	1868 KB	Output is correct
19	Correct	1 ms	1868 KB	Output is correct
20	Correct	6 ms	1868 KB	Output is correct
21	Correct	3 ms	1868 KB	Output is correct
22	Correct	4 ms	1868 KB	Output is correct
23	Correct	5 ms	1868 KB	Output is correct
24	Correct	4 ms	1868 KB	Output is correct
25	Correct	2 ms	1868 KB	Output is correct
26	Correct	747 ms	1948 KB	Output is correct
27	Correct	1 ms	1868 KB	Output is correct
28	Correct	2 ms	1856 KB	Output is correct
29	Execution timed out	1092 ms	1868 KB	Time limit exceeded
30	Halted	0 ms	0 KB	-