Submission #874958

#	Time	Username	Problem	Language	Result	Execution time	Memory
874958		TAhmed33	Kitchen (BOI19_kitchen)	C++98	100 / 100	54 ms	106408 KiB

kitchen

#include <bits/stdc++.h>
using namespace std;
int n, m, k, a[301], b[301];
int dp[301][90001];
void bad () {
	cout << "Impossible\n";
	exit(0);
}
int main () {
	cin >> n >> m >> k;
	for (int i = 0; i < n; i++) cin >> a[i];
	for (int j = 0; j < m; j++) cin >> b[j];
	int pp = *min_element(a, a + n);
	if (pp < k || m < k) bad();
	for (int i = 1; i <= 90000; i++) dp[0][i] = -1e9;
	for (int i = 1; i <= m; i++) {
		for (int j = 0; j <= 90000; j++) {
			if (j < b[i - 1]) {
				dp[i][j] = dp[i - 1][j]; continue;
			}
			dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - b[i - 1]] + min(b[i - 1], n));
		}
	}
	int mn = 1e9; int sum = 0; for (int i = 0; i < n; i++) sum += a[i];
	for (int i = sum; i <= 90000; i++) {
		if (dp[m][i] >= n * k) {
			mn = i; break;
		}
	}
	mn -= sum;
	if (mn >= 1e8) bad();
	cout << mn << '\n';
}

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