oj.uz

Submission #124855

# Submission time Handle Problem Language Result Execution time Memory
124855 2019-07-04T04:35:50 Z 윤교준(#3050) Kitchen (BOI19_kitchen) C++14
52 / 100
 80 ms 2040 KB 
#include <bits/stdc++.h>
#define eb emplace_back
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
#define befv(V) ((V)[sz(V)-2])
#define upmax(a,b) (a)=max((a),(b))
#define INF (0x3f3f3f3f)
using namespace std;
typedef long long ll;
inline void fuk() { puts("Impossible"); exit(0); }

bitset<4505> D[4505];

int A[305], B[305];

int N, M, K, Asum;

int main() {
	ios::sync_with_stdio(false);

	cin >> N >> M >> K;
	if(M < K) fuk();
	for(int i = 1; i <= N; i++) {
		cin >> A[i];
		if(A[i] < K) fuk();
		Asum += A[i];
	}
	for(int i = 1; i <= M; i++) cin >> B[i];
	sort(B+1, B+M+1);

	D[0][0] = true;
	for(int i = 1, sum = 0; i <= M; i++) {
		for(int bsum = sum; 0 <= bsum; bsum--) {
			for(int cnt = N*K; 0 <= cnt; cnt--)
				if(D[bsum][cnt])
					D[bsum+B[i]][min(N*K, cnt + min(B[i], N))] = true;
		}
		sum += B[i];
	}

	for(int i = Asum; i < 4505; i++)
		if(D[i][N*K]) {
			cout << i-Asum << endl;
			exit(0);
		}
	fuk();
	return 0;
}

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 376 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 376 KB Output is correct
8 Correct 3 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 376 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 376 KB Output is correct
8 Correct 3 ms 376 KB Output is correct
9 Correct 6 ms 1912 KB Output is correct
10 Correct 4 ms 760 KB Output is correct
11 Correct 3 ms 504 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 80 ms 2040 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 19 ms 632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 1016 KB Output is correct
2 Correct 14 ms 760 KB Output is correct
3 Correct 24 ms 1016 KB Output is correct
4 Correct 60 ms 1116 KB Output is correct
5 Correct 2 ms 380 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 376 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 376 KB Output is correct
8 Correct 3 ms 376 KB Output is correct
9 Correct 6 ms 1912 KB Output is correct
10 Correct 4 ms 760 KB Output is correct
11 Correct 3 ms 504 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 80 ms 2040 KB Output is correct
14 Runtime error 19 ms 632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Halted 0 ms 0 KB -