Submission #921103

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
921103	2024-02-03T10:16:37 Z	shoryu386	Kitchen (BOI19_kitchen)	C++17	72 / 100	202 ms	262144 KB

kitchen

#include <bits/stdc++.h>
using namespace std;
 
#define int long long
 
main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	
	int n, m, k; cin >> n >> m >> k;
	
	int buckets[n], balls[m];
	
	for (int x = 0; x < n; x++) cin >> buckets[x];
	for (int x = 0; x < m; x++) cin >> balls[x];
	
	#define IMP cout << "Impossible"; return 0;
	
	bool dead = false;
	for (int x = 0; x < n; x++){
		if (buckets[x] < k){
			dead = true;
		}
	}
	if (dead) {IMP;}
	
	int bucketsum = 0;
	for (int x = 0; x < n; x++){
		bucketsum += buckets[x];
	}
	
	
	#define BSMAX 100000
	bitset<BSMAX> hmm[n*k+1];
	
	hmm[n*k][0] = 1;
	
	for (int x = 0; x < m; x++){
		for (int z = 0; z <= n*k; z++){
			hmm[max(0LL, z - min(balls[x], n))] |= (hmm[z] << balls[x]);
		}
	}
	int ans = -1;
	for (int x = bucketsum; x < BSMAX; x++){
		if (hmm[0][x]){
			ans = x-bucketsum;
			break;
		}
	}
		
	if (ans == -1) cout << "Impossible";
	else cout << ans;
	
}

Compilation message

kitchen.cpp:6:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
    6 | main(){
      | ^~~~

Subtask #1

9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Correct	1 ms	860 KB	Output is correct
5	Correct	4 ms	3928 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	1 ms	596 KB	Output is correct

Subtask #2

22.0 / 22.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Correct	1 ms	860 KB	Output is correct
5	Correct	4 ms	3928 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	1 ms	596 KB	Output is correct
9	Correct	3 ms	1372 KB	Output is correct
10	Correct	1 ms	604 KB	Output is correct
11	Correct	9 ms	3420 KB	Output is correct
12	Correct	6 ms	2140 KB	Output is correct
13	Correct	123 ms	26096 KB	Output is correct

Subtask #3

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	170 ms	4100 KB	Output is correct
2	Correct	148 ms	4100 KB	Output is correct
3	Correct	193 ms	4084 KB	Output is correct
4	Correct	184 ms	3908 KB	Output is correct
5	Correct	190 ms	3928 KB	Output is correct
6	Correct	147 ms	4096 KB	Output is correct

Subtask #4

21.0 / 21.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	76 ms	10004 KB	Output is correct
2	Correct	77 ms	8540 KB	Output is correct
3	Correct	68 ms	8796 KB	Output is correct
4	Correct	202 ms	18572 KB	Output is correct
5	Correct	0 ms	344 KB	Output is correct

Subtask #5

0 / 28.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Correct	1 ms	860 KB	Output is correct
5	Correct	4 ms	3928 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	1 ms	596 KB	Output is correct
9	Correct	3 ms	1372 KB	Output is correct
10	Correct	1 ms	604 KB	Output is correct
11	Correct	9 ms	3420 KB	Output is correct
12	Correct	6 ms	2140 KB	Output is correct
13	Correct	123 ms	26096 KB	Output is correct
14	Correct	170 ms	4100 KB	Output is correct
15	Correct	148 ms	4100 KB	Output is correct
16	Correct	193 ms	4084 KB	Output is correct
17	Correct	184 ms	3908 KB	Output is correct
18	Correct	190 ms	3928 KB	Output is correct
19	Correct	147 ms	4096 KB	Output is correct
20	Correct	76 ms	10004 KB	Output is correct
21	Correct	77 ms	8540 KB	Output is correct
22	Correct	68 ms	8796 KB	Output is correct
23	Correct	202 ms	18572 KB	Output is correct
24	Correct	0 ms	344 KB	Output is correct
25	Runtime error	141 ms	262144 KB	Execution killed with signal 9
26	Halted	0 ms	0 KB	-