제출 #874958

#제출 시각아이디문제언어결과실행 시간메모리
874958TAhmed33Kitchen (BOI19_kitchen)C++98
100 / 100
54 ms106408 KiB
#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';
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...