oj.uz

Submission #522776

# Submission time Handle Problem Language Result Execution time Memory
522776 2022-02-05T18:30:03 Z LucaDantas Kitchen (BOI19_kitchen) C++17
0 / 100
 22 ms 588 KB 
#include <cstdio>

constexpr int maxn = 310, inf = 0x3f3f3f3f;

int a[maxn], b[maxn], ex[maxn];

int dp[maxn*maxn];

int main() {
	int n, m, k; scanf("%d %d %d", &n, &m, &k);
	for(int i = 0; i < n; i++)
		scanf("%d", a+i);
	for(int i = 0; i < m; i++)
		scanf("%d", b+i);

	int soma = 0;
	for(int i = 0; i < n; i++) {
		soma += a[i];
		if(a[i] < k) return puts("impossible"), 0;
	}

	auto max = [](int a, int b) { return a > b ? a : b; };
	auto min = [](int a, int b) { return a < b ? a : b; };

	int max_val = 0;
	for(int i = 0; i < m; i++)
		max_val += b[i];

	for(int i = 0; i <= max_val; i++)
		dp[i] = -inf;
	dp[0] = 0;

	for(int i = 0; i < m; i++)
		for(int j = max_val-b[i]; j >= 0; j--)
			dp[j+b[i]] = max(dp[j+b[i]], dp[j] + min(n, b[i]));

	int ans = -1;
	for(int i = soma; i <= max_val; i++)
		if(dp[i] >= n*k) { ans = i - soma; break; }

	if(ans == -1) puts("impossible");
	else printf("%d\n", ans);
}

Compilation message

kitchen.cpp: In function 'int main()':
kitchen.cpp:10:20: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 |  int n, m, k; scanf("%d %d %d", &n, &m, &k);
      |               ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
kitchen.cpp:12:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 |   scanf("%d", a+i);
      |   ~~~~~^~~~~~~~~~~
kitchen.cpp:14:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   14 |   scanf("%d", b+i);
      |   ~~~~~^~~~~~~~~~~

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 280 KB Output is correct
6 Incorrect 0 ms 204 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 280 KB Output is correct
6 Incorrect 0 ms 204 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 516 KB Output is correct
2 Correct 13 ms 504 KB Output is correct
3 Correct 12 ms 468 KB Output is correct
4 Correct 22 ms 588 KB Output is correct
5 Incorrect 21 ms 588 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Incorrect 0 ms 204 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 280 KB Output is correct
6 Incorrect 0 ms 204 KB Output isn't correct
7 Halted 0 ms 0 KB -