제출 #1187226

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1187226		tamyte	Kitchen (BOI19_kitchen)	C++20	100 / 100	85 ms	100752 KiB

kitchen

#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";
}

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