oj.uz

Submission #554587

# Submission time Handle Problem Language Result Execution time Memory
554587 2022-04-28T19:48:47 Z kenjinemera Knapsack (NOI18_knapsack) C++17
29 / 100
 2 ms 3412 KB 
#include <bits/stdc++.h>

using namespace std;

const int maxn = 50002, maxs = 2001;

long long dp[maxn][maxs][2];

int main() {
	int s, n;

	struct item
	{
		int v, w, k;
	};

	cin >> s >> n;

	struct item arr[n+1];

	// v -> value
	// w -> weight
	// k -> copies

	for (int i = 1; i <= n; i++) {
		int a, b, c;
		cin >> a >> b >> c;

		arr[i] = {a,b,c};
	}

	// we find that our dp array will have 3 dimensions of [n][w]

	// at dp[i][j] -> we find the number of item i used to have a total value of j

	long long ans = 0;
	
	// practice with a 0-1 knapsack
	for (int i = 1; i <= n; i++)
	{
		for (int j = 0; j <= s; j++)  
		{
			/* 
			 	we must keep weight in mind
			       	we must keep the number of uses of the current item in mind	
				
				a cell can either be reached from an earlier state in the same row or through the row above j
			*/		
            dp[i][j][0] = dp[i-1][j][0];            

			if (j - arr[i].w >= 0) {
				long long trans = dp[i-1][j-arr[i].w][0] + (long long)arr[i].v;
				if (trans >= dp[i][j][0]) 
				{
					dp[i][j][0] = trans; 
					dp[i][j][1] = 1;
				}
            }


			if (j - arr[i].w >= 0 && dp[i][j-arr[i].w][1] < arr[i].k) {
				long long trans = dp[i][j-arr[i].w][0] + (long long)arr[i].v;
				if (trans > dp[i][j][0]) 
				{
					dp[i][j][0] = trans; 
					dp[i][j][1] = dp[i][j - arr[i].w][1] + 1;
				} else if (trans == dp[i][j][0]) {
					dp[i][j][1] = min(dp[i][j-arr[i].w][1] + 1, dp[i][j][1]); 
				}
			}

			ans = max(ans, dp[i][j][0]);
		}
	}

	cout << ans << "\n";
	
	return 0;
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 724 KB Output is correct
2 Correct 2 ms 3412 KB Output is correct
3 Correct 2 ms 3284 KB Output is correct
4 Correct 2 ms 3412 KB Output is correct
5 Correct 2 ms 3284 KB Output is correct
6 Correct 2 ms 3284 KB Output is correct
7 Correct 2 ms 3316 KB Output is correct
8 Correct 2 ms 3284 KB Output is correct
9 Correct 2 ms 3284 KB Output is correct
10 Correct 2 ms 3412 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 724 KB Output is correct
2 Correct 2 ms 3412 KB Output is correct
3 Correct 2 ms 3284 KB Output is correct
4 Correct 2 ms 3412 KB Output is correct
5 Correct 2 ms 3284 KB Output is correct
6 Correct 2 ms 3284 KB Output is correct
7 Correct 2 ms 3316 KB Output is correct
8 Correct 2 ms 3284 KB Output is correct
9 Correct 2 ms 3284 KB Output is correct
10 Correct 2 ms 3412 KB Output is correct
11 Correct 1 ms 596 KB Output is correct
12 Incorrect 2 ms 3284 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 724 KB Output is correct
6 Correct 2 ms 3412 KB Output is correct
7 Correct 2 ms 3284 KB Output is correct
8 Correct 2 ms 3412 KB Output is correct
9 Correct 2 ms 3284 KB Output is correct
10 Correct 2 ms 3284 KB Output is correct
11 Correct 2 ms 3316 KB Output is correct
12 Correct 2 ms 3284 KB Output is correct
13 Correct 2 ms 3284 KB Output is correct
14 Correct 2 ms 3412 KB Output is correct
15 Correct 1 ms 596 KB Output is correct
16 Incorrect 2 ms 3284 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 724 KB Output is correct
6 Correct 2 ms 3412 KB Output is correct
7 Correct 2 ms 3284 KB Output is correct
8 Correct 2 ms 3412 KB Output is correct
9 Correct 2 ms 3284 KB Output is correct
10 Correct 2 ms 3284 KB Output is correct
11 Correct 2 ms 3316 KB Output is correct
12 Correct 2 ms 3284 KB Output is correct
13 Correct 2 ms 3284 KB Output is correct
14 Correct 2 ms 3412 KB Output is correct
15 Correct 1 ms 596 KB Output is correct
16 Incorrect 2 ms 3284 KB Output isn't correct
17 Halted 0 ms 0 KB -