제출 #1187226

#제출 시각아이디문제언어결과실행 시간메모리
1187226tamyteKitchen (BOI19_kitchen)C++20
100 / 100
85 ms100752 KiB
#include <bits/stdc++.h>


using namespace std;
int a[301], b[301];
int main() {
	int n, m, k;
	cin >> n >> m >> k;
	if (k > m) {
		cout << "Impossible\n";
		return 0;
	}
	int sum = 0, need = 0;
	for (int i = 0; i < n; ++i) {
		cin >> a[i];
		if (a[i] < k) {
			cout << "Impossible\n";
			return 0;
		}
		need += a[i];
	}
	for (int i = 0; i < m; ++i) {
		cin >> b[i];
		sum += b[i];
	}
	vector<vector<int>> dp(m + 1, vector<int>(sum + 1, INT_MIN));
	dp[0][0] = 0;
	for (int i = 0; i < m; ++i) {
		for (int j = 0; j <= sum; ++j) {
			dp[i + 1][j] = max(dp[i + 1][j], dp[i][j]);
		}
		for (int j = sum; j >= b[i]; --j) {
			dp[i + 1][j] = max(dp[i + 1][j], dp[i][j - b[i]] + min(n, b[i]));
		}
	}
	// for (int j = 0; j <= m; ++j) {
		// for (int i = 0; i <= sum; ++i) {
			// if (dp[j][i] < 0) cout << "- ";
			// else cout << dp[j][i] << " ";
		// }
		// cout << endl;
	// }
	// cout << endl;
	for (int i = need; i <= sum; ++i) {
		if (dp[m][i] < n * k) continue;
		cout << i - need << endl;
		return 0;
	}
	cout << "Impossible\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...