Submission #746041

#	Time	Username	Problem	Language	Result	Execution time	Memory
746041		vjudge1	Kitchen (BOI19_kitchen)	C++17	51 / 100	326 ms	108404 KiB

kitchen

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 301;
const int MAXS = MAXN*MAXN+1000;

int dp[MAXN][MAXS], n, m, k;

void solve() {
	vector<int> a(n+1), b(m+1);
	int need = 0;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		need += a[i];
	}
	for (int j = 1; j <= m; j++) {
		cin >> b[j];
	}
	
	int ans = INT_MAX;
	for (int bits = 0; bits < (1 << m); bits++) {
		int x = bits<<1;
		
		int sum = 0, chefs = 0, bad_chefs = 0, good_chefs = 0;
		for (int i = 1; i <= m; i++) {
			if ((x>>i)&1) {
				sum += b[i]; chefs++;
				if (b[i] < n) bad_chefs += b[i];
				else good_chefs++;
			}
		}

		bool good = int(bad_chefs/n) + good_chefs >= k;
		for (int i = 1; i <= n; i++) {
			if (a[i] < k) good = false;
		}
		
		if (good && sum >= need) {
			ans = min(ans, sum-need);
		}

	}
	if (ans == INT_MAX)
		cout << "Impossible\n";
	else
		cout << ans << "\n";
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> n >> m >> k;
	if (k != 1) {
		solve();
		return 0;
	}
	vector<int> a(n+1), b(m+1);
	int sum = 0;
	for (int i = 1; i <= n; i++) {
		cin >> a[i]; sum += a[i];
	}
	for (int j = 1; j <= m; j++) {
		cin >> b[j];
	}
	
	dp[0][0] = true;
	for (int i = 1; i <= m; i++) {
		for (int j = 0; j < MAXS; j++) {
			dp[i][j] = dp[i-1][j];
		}
		for (int j = b[i]; j < MAXS; j++) {
			if (dp[i-1][j-b[i]]) {
				dp[i][j] = true;
			}
		}
	}
	for (int i = 0; i < MAXS; i++) {
		if (dp[m][i]) cerr << i << " ";
	}
	for (int i = sum; i < MAXS; i++) {
		if (dp[m][i]) {
			cout << i-sum << "\n";
			return 0;
		}
	}
	cout << "Impossible\n";
	return 0;
}

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