oj.uz

Submission #595653

# Submission time Handle Problem Language Result Execution time Memory
595653 2022-07-13T22:54:36 Z UncoolAnon Kitchen (BOI19_kitchen) C++14
100 / 100
 478 ms 106804 KB 
#include <bits/stdc++.h> 
 
#define pii pair<int,int> 
#define F first 
#define S second 
#define mp make_pair 
 
using namespace std; 

const int inf=1e9; 

int main(){
	int n,m,k; 
	cin>>n>>m>>k;
	vector<int> a(n); 
	for(int&x:a) cin>>x; 
	vector<int> c(m); 
	for(int&x:c) cin>>x; 
	int s=0; 
	for(int&x:a){
		s+=x; 
		if(k>x){
			cout<<"Impossible"; 
			return 0; 
		}
	}
	vector<vector<int>> mem(m+1,vector<int>(300*300+1,-1)); 
	function<int(int,int)> dp=[&](int index,int sum){
		if(index==m&&sum==0) return 0; 
		if(index==m) return -inf;
		if(mem[index][sum]!=-1) return mem[index][sum];
		return mem[index][sum]=max(dp(index+1,sum),(sum>=c[index]?dp(index+1,sum-c[index])+min(c[index],n):-inf));
	}; 
	for(int i=s;i<=300*300;i++)
		if(dp(0,i)>=k*n){
			cout<<i-s;
			return 0; 
		}
	cout<<"Impossible";
	return 0; 
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1620 KB Output is correct
2 Correct 1 ms 1620 KB Output is correct
3 Correct 1 ms 1620 KB Output is correct
4 Correct 1 ms 1708 KB Output is correct
5 Correct 1 ms 1704 KB Output is correct
6 Correct 0 ms 304 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 5 ms 1620 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1620 KB Output is correct
2 Correct 1 ms 1620 KB Output is correct
3 Correct 1 ms 1620 KB Output is correct
4 Correct 1 ms 1708 KB Output is correct
5 Correct 1 ms 1704 KB Output is correct
6 Correct 0 ms 304 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 5 ms 1620 KB Output is correct
9 Correct 4 ms 6228 KB Output is correct
10 Correct 4 ms 6228 KB Output is correct
11 Correct 30 ms 6228 KB Output is correct
12 Correct 3 ms 6228 KB Output is correct
13 Correct 3 ms 6228 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 162 ms 92992 KB Output is correct
2 Correct 100 ms 80676 KB Output is correct
3 Correct 225 ms 106804 KB Output is correct
4 Correct 351 ms 106700 KB Output is correct
5 Correct 404 ms 103216 KB Output is correct
6 Correct 127 ms 74300 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 15060 KB Output is correct
2 Correct 7 ms 15060 KB Output is correct
3 Correct 7 ms 15016 KB Output is correct
4 Correct 10 ms 15124 KB Output is correct
5 Correct 0 ms 212 KB Output is correct

Subtask #5
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1620 KB Output is correct
2 Correct 1 ms 1620 KB Output is correct
3 Correct 1 ms 1620 KB Output is correct
4 Correct 1 ms 1708 KB Output is correct
5 Correct 1 ms 1704 KB Output is correct
6 Correct 0 ms 304 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 5 ms 1620 KB Output is correct
9 Correct 4 ms 6228 KB Output is correct
10 Correct 4 ms 6228 KB Output is correct
11 Correct 30 ms 6228 KB Output is correct
12 Correct 3 ms 6228 KB Output is correct
13 Correct 3 ms 6228 KB Output is correct
14 Correct 162 ms 92992 KB Output is correct
15 Correct 100 ms 80676 KB Output is correct
16 Correct 225 ms 106804 KB Output is correct
17 Correct 351 ms 106700 KB Output is correct
18 Correct 404 ms 103216 KB Output is correct
19 Correct 127 ms 74300 KB Output is correct
20 Correct 7 ms 15060 KB Output is correct
21 Correct 7 ms 15060 KB Output is correct
22 Correct 7 ms 15016 KB Output is correct
23 Correct 10 ms 15124 KB Output is correct
24 Correct 0 ms 212 KB Output is correct
25 Correct 299 ms 74956 KB Output is correct
26 Correct 478 ms 86624 KB Output is correct
27 Correct 80 ms 57428 KB Output is correct
28 Correct 188 ms 86944 KB Output is correct
29 Correct 252 ms 89168 KB Output is correct
30 Correct 353 ms 106744 KB Output is correct