oj.uz

Submission #746041

# Submission time Handle Problem Language Result Execution time Memory
746041 2023-05-21T10:43:52 Z vjudge1 Kitchen (BOI19_kitchen) C++17
51 / 100
 326 ms 108404 KB 
#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.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 980 KB Output is correct
2 Correct 2 ms 980 KB Output is correct
3 Correct 1 ms 980 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 2 ms 980 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 980 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 980 KB Output is correct
2 Correct 2 ms 980 KB Output is correct
3 Correct 1 ms 980 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 2 ms 980 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 980 KB Output is correct
9 Correct 3 ms 320 KB Output is correct
10 Correct 2 ms 212 KB Output is correct
11 Correct 3 ms 212 KB Output is correct
12 Correct 3 ms 324 KB Output is correct
13 Correct 10 ms 212 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 151 ms 93960 KB Output is correct
2 Correct 146 ms 81448 KB Output is correct
3 Correct 188 ms 108028 KB Output is correct
4 Correct 326 ms 108404 KB Output is correct
5 Correct 267 ms 104652 KB Output is correct
6 Correct 107 ms 74948 KB Output is correct

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 980 KB Output is correct
2 Correct 2 ms 980 KB Output is correct
3 Correct 1 ms 980 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 2 ms 980 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 980 KB Output is correct
9 Correct 3 ms 320 KB Output is correct
10 Correct 2 ms 212 KB Output is correct
11 Correct 3 ms 212 KB Output is correct
12 Correct 3 ms 324 KB Output is correct
13 Correct 10 ms 212 KB Output is correct
14 Correct 151 ms 93960 KB Output is correct
15 Correct 146 ms 81448 KB Output is correct
16 Correct 188 ms 108028 KB Output is correct
17 Correct 326 ms 108404 KB Output is correct
18 Correct 267 ms 104652 KB Output is correct
19 Correct 107 ms 74948 KB Output is correct
20 Incorrect 0 ms 212 KB Output isn't correct
21 Halted 0 ms 0 KB -