oj.uz

Submission #133033

# Submission time Handle Problem Language Result Execution time Memory
133033 2019-07-20T05:30:27 Z E869120 Kitchen (BOI19_kitchen) C++14
72 / 100
 229 ms 34936 KB 
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int N, M, K, S, A[309], B[309];
bool dp[309][90009];
bool dp1[49][1609][1609];

int solve(vector<int>R) {
	int s1 = 0, s2 = 0;
	for (int i = 0; i < R.size(); i++) {
		s1 += min(N, R[i]);
		s2 += R[i];
	}
	if (s1 < N * K) return (1 << 30);
	if (s2 < S) return (1 << 30);
	return s2 - S;
}

int solve_subtask3() {
	dp[0][0] = true;
	for (int i = 0; i < M; i++) {
		for (int j = 0; j <= 90000; j++) {
			if (dp[i][j] == false) continue;
			dp[i + 1][j] = true;
			dp[i + 1][j + B[i]] = true;
		}
	}
	for (int i = S; i <= 90000; i++) {
		if (dp[M][i] == true) return i - S;
	}
	return (1 << 30);
}

int solve_subtask4() {
	dp1[0][0][0] = true;
	for (int i = 0; i < M; i++) {
		for (int j = 0; j <= 1600; j++) {
			for (int k = 0; k <= 1600; k++) {
				if (dp1[i][j][k] == false) continue;
				dp1[i + 1][j][k] = true;
				dp1[i + 1][j + min(N, B[i])][k + B[i]] = true;
			}
		}
	}
	for (int i = S; i <= 1600; i++) {
		for (int j = N * K; j <= 1600; j++) {
			if (dp1[M][j][i] == true) return i - S;
		}
	}
	return (1 << 30);
}

int main() {
	cin >> N >> M >> K;
	for (int i = 0; i < N; i++) {
		cin >> A[i]; S += A[i];
		if (A[i] < K) {
			cout << "Impossible" << endl;
			return 0;
		}
	}
	for (int i = 0; i < M; i++) cin >> B[i];

	if (K == 1) {
		int ans = solve_subtask3();
		if (ans == (1 << 30)) cout << "Impossible" << endl;
		else cout << ans << endl;
	}
	else if (M <= 15) {
		int ans = (1 << 30);
		for (int i = 0; i < (1 << M); i++) {
			vector<int> vec;
			for (int j = 0; j < M; j++) {
				if ((i / (1 << j)) % 2 == 1) vec.push_back(B[j]);
			}
			int ret = solve(vec);
			ans = min(ans, ret);
		}
		if (ans == (1 << 30)) cout << "Impossible" << endl;
		else cout << ans << endl;
	}
	else {
		int ans = solve_subtask4();
		if (ans == (1 << 30)) cout << "Impossible" << endl;
		else cout << ans << endl;
	}
	return 0;
}

Compilation message

kitchen.cpp: In function 'int solve(std::vector<int>)':
kitchen.cpp:12:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < R.size(); i++) {
                  ~~^~~~~~~~~~

Subtask #1
9.0 / 9.0

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

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 16 ms 256 KB Output is correct
10 Correct 16 ms 348 KB Output is correct
11 Correct 16 ms 364 KB Output is correct
12 Correct 16 ms 364 KB Output is correct
13 Correct 17 ms 476 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 9880 KB Output is correct
2 Correct 35 ms 7544 KB Output is correct
3 Correct 58 ms 8800 KB Output is correct
4 Correct 72 ms 13688 KB Output is correct
5 Correct 66 ms 13688 KB Output is correct
6 Correct 33 ms 6264 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 12396 KB Output is correct
2 Correct 137 ms 22708 KB Output is correct
3 Correct 140 ms 34936 KB Output is correct
4 Correct 139 ms 33144 KB Output is correct
5 Correct 2 ms 256 KB Output is correct

Subtask #5
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 16 ms 256 KB Output is correct
10 Correct 16 ms 348 KB Output is correct
11 Correct 16 ms 364 KB Output is correct
12 Correct 16 ms 364 KB Output is correct
13 Correct 17 ms 476 KB Output is correct
14 Correct 43 ms 9880 KB Output is correct
15 Correct 35 ms 7544 KB Output is correct
16 Correct 58 ms 8800 KB Output is correct
17 Correct 72 ms 13688 KB Output is correct
18 Correct 66 ms 13688 KB Output is correct
19 Correct 33 ms 6264 KB Output is correct
20 Correct 129 ms 12396 KB Output is correct
21 Correct 137 ms 22708 KB Output is correct
22 Correct 140 ms 34936 KB Output is correct
23 Correct 139 ms 33144 KB Output is correct
24 Correct 2 ms 256 KB Output is correct
25 Runtime error 229 ms 23608 KB Execution killed with signal 11 (could be triggered by violating memory limits)
26 Halted 0 ms 0 KB -