oj.uz

Submission #644490

# Submission time Handle Problem Language Result Execution time Memory
644490 2022-09-24T17:59:45 Z amoorj Kitchen (BOI19_kitchen) C++17
100 / 100
 83 ms 109252 KB 
//#pragma GCC optimize ("O3,unroll-loops,Ofast")
//#pragma GCC target ("avx2,bmi,bmi2,popcnt")
#include <bits/stdc++.h>
#define F first
#define pb push_back
#define sz size()
#define S second
using namespace std;
typedef long long int ll;

const int N = 303, INF = 2e9;
int n,k,m,a[N],b[N],dp[N][N*N],sum = 0;

inline void init(){
	for(int i=0;i<N;i++)
		for(int j=0;j<N*N;j++)
			dp[i][j] = -INF;
}
inline void input(){
	cin >> n >> m >> k;
	for(int i=0;i<n;i++){
		cin >> a[i];
		sum += a[i];
	}
	for(int i=0;i<m;i++)
		cin >> b[i];
}
inline void solve(){
	dp[0][0] = 0;
	for(int i=0;i<m;i++){
		for(int j=0;j<N*N;j++){	
			dp[i+1][j] = dp[i][j];
			if(j >= b[i])
				dp[i+1][j] = max(dp[i+1][j], dp[i][j-b[i]] + min(b[i], n));
		}
	}
	for(int i=0;i<n;i++){
		if(a[i] < k){	
			cout << "Impossible";
			return;
		}
	}
	for(int j=sum;j<N*N;j++){
		if(dp[m][j] >= n*k){
			cout << j - sum;
			return;
		}
	}
	cout << "Impossible";
}
int main(){
	ios:: sync_with_stdio(0), cin.tie(0), cout.tie(0);
//	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
	init();
	int queries = 1;
//	cin >> queries;
	while(queries--){
		input();
		solve();
	}
	return 0;
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 109132 KB Output is correct
2 Correct 51 ms 109172 KB Output is correct
3 Correct 49 ms 109132 KB Output is correct
4 Correct 47 ms 109076 KB Output is correct
5 Correct 48 ms 109132 KB Output is correct
6 Correct 47 ms 109156 KB Output is correct
7 Correct 49 ms 109072 KB Output is correct
8 Correct 49 ms 109140 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 109132 KB Output is correct
2 Correct 51 ms 109172 KB Output is correct
3 Correct 49 ms 109132 KB Output is correct
4 Correct 47 ms 109076 KB Output is correct
5 Correct 48 ms 109132 KB Output is correct
6 Correct 47 ms 109156 KB Output is correct
7 Correct 49 ms 109072 KB Output is correct
8 Correct 49 ms 109140 KB Output is correct
9 Correct 48 ms 109060 KB Output is correct
10 Correct 49 ms 109176 KB Output is correct
11 Correct 48 ms 109172 KB Output is correct
12 Correct 49 ms 109076 KB Output is correct
13 Correct 50 ms 109132 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 109180 KB Output is correct
2 Correct 79 ms 109196 KB Output is correct
3 Correct 80 ms 109128 KB Output is correct
4 Correct 83 ms 109112 KB Output is correct
5 Correct 83 ms 109180 KB Output is correct
6 Correct 71 ms 109252 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 109144 KB Output is correct
2 Correct 53 ms 109176 KB Output is correct
3 Correct 53 ms 109068 KB Output is correct
4 Correct 52 ms 109156 KB Output is correct
5 Correct 59 ms 109148 KB Output is correct

Subtask #5
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 109132 KB Output is correct
2 Correct 51 ms 109172 KB Output is correct
3 Correct 49 ms 109132 KB Output is correct
4 Correct 47 ms 109076 KB Output is correct
5 Correct 48 ms 109132 KB Output is correct
6 Correct 47 ms 109156 KB Output is correct
7 Correct 49 ms 109072 KB Output is correct
8 Correct 49 ms 109140 KB Output is correct
9 Correct 48 ms 109060 KB Output is correct
10 Correct 49 ms 109176 KB Output is correct
11 Correct 48 ms 109172 KB Output is correct
12 Correct 49 ms 109076 KB Output is correct
13 Correct 50 ms 109132 KB Output is correct
14 Correct 76 ms 109180 KB Output is correct
15 Correct 79 ms 109196 KB Output is correct
16 Correct 80 ms 109128 KB Output is correct
17 Correct 83 ms 109112 KB Output is correct
18 Correct 83 ms 109180 KB Output is correct
19 Correct 71 ms 109252 KB Output is correct
20 Correct 63 ms 109144 KB Output is correct
21 Correct 53 ms 109176 KB Output is correct
22 Correct 53 ms 109068 KB Output is correct
23 Correct 52 ms 109156 KB Output is correct
24 Correct 59 ms 109148 KB Output is correct
25 Correct 71 ms 109100 KB Output is correct
26 Correct 74 ms 109184 KB Output is correct
27 Correct 70 ms 109180 KB Output is correct
28 Correct 74 ms 109128 KB Output is correct
29 Correct 78 ms 109132 KB Output is correct
30 Correct 79 ms 109120 KB Output is correct