Submission #160603

#	Time	Username	Problem	Language	Result	Execution time	Memory
160603		luciocf	Kitchen (BOI19_kitchen)	C++14	100 / 100	43 ms	760 KiB

kitchen

#include <bits/stdc++.h>

using namespace std;

const int maxn = 310;
const int maxs = 9e4+10;
const int inf = 1e9+10;

int n, m, k, tot;

int a[maxn], b[maxn];

int dp[maxs];

int main(void)
{
	scanf("%d %d %d", &n, &m, &k);

	for (int i = 1; i <= n; i++)
	{
		scanf("%d", &a[i]);
		tot += a[i];
	}

	for (int i = 1; i <= m; i++)
		scanf("%d", &b[i]);

	for (int i = 1; i <= n; i++)
	{
		if (a[i] < k)
		{
			printf("Impossible\n");
			return 0;
		}
	}

	for (int i = 1; i < maxs; i++)
		dp[i] = -inf;

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

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

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

Compilation message (stderr)

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

• Subtask 1: 9 / 9
• Subtask 2: 22 / 22
• Subtask 3: 20 / 20
• Subtask 4: 21 / 21
• Subtask 5: 28 / 28