oj.uz

Submission #652361

# Submission time Handle Problem Language Result Execution time Memory
652361 2022-10-22T08:59:17 Z beaconmc Kitchen (BOI19_kitchen) C++14
100 / 100
 166 ms 212464 KB 
#include <bits/stdc++.h>

typedef long long ll;
using namespace std;

#define FOR(i, x, y) for(ll i=x; i<y; i++)
#define FORNEG(i, x, y) for(ll i=x; i>y; i--)
#define fast() ios_base::sync_with_stdio(false);cin.tie(NULL)

ll n,m,k;

ll dp[301][90001];
ll meal[301];
ll chefs[301];
ll sum = 0;
ll sum2 = 0;
int main(){
	FOR(i,0,301) FOR(j,0,90001) dp[i][j] = -1;

	cin >> n >> m >> k;
	FOR(i,0,n){
		cin >> meal[i];
		sum += meal[i];
	}
	FOR(i,0,m){
		cin >> chefs[i];
		sum2 += chefs[i];
	}

	FOR(i,0,n){
		if (meal[i] < k){
			cout << "Impossible";
			return 0;
		}
	}
	ll temp = 0;
	FOR(i,0,m){
		temp += min(n, chefs[i]);
	}
	if (temp < n*k){
		cout << "Impossible";
		return 0;
	}
	if (sum > sum2){
		cout << "Impossible";
		return 0;
	}

	dp[0][0] = 0;

	FOR(i,0,m){
		FOR(j,0,90001){
			if (dp[i][j] == -1) continue;

			if (dp[i+1][j+chefs[i]] == -1){
				dp[i+1][j+chefs[i]] = min(n, chefs[i]) + dp[i][j];
			}else{
				dp[i+1][j+chefs[i]] = max(dp[i+1][j+chefs[i]], min(n, chefs[i]) + dp[i][j]);
			}
			dp[i+1][j] = max(dp[i][j], dp[i+1][j]);
		}

	}
	ll ans = 100000000000;

	FOR(i,0,301) FOR(j,0,90001){
		if (dp[i][j] == -1) continue;
		if (dp[i][j] < n*k) continue;
		if (j<sum) continue;
		ans = min(ans, j-sum);
	}
	cout << ans << endl;
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 212300 KB Output is correct
2 Correct 136 ms 212344 KB Output is correct
3 Correct 134 ms 212276 KB Output is correct
4 Correct 137 ms 212292 KB Output is correct
5 Correct 131 ms 212344 KB Output is correct
6 Correct 101 ms 212276 KB Output is correct
7 Correct 79 ms 212264 KB Output is correct
8 Correct 81 ms 212268 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 212300 KB Output is correct
2 Correct 136 ms 212344 KB Output is correct
3 Correct 134 ms 212276 KB Output is correct
4 Correct 137 ms 212292 KB Output is correct
5 Correct 131 ms 212344 KB Output is correct
6 Correct 101 ms 212276 KB Output is correct
7 Correct 79 ms 212264 KB Output is correct
8 Correct 81 ms 212268 KB Output is correct
9 Correct 108 ms 212348 KB Output is correct
10 Correct 109 ms 212300 KB Output is correct
11 Correct 81 ms 212324 KB Output is correct
12 Correct 108 ms 212224 KB Output is correct
13 Correct 109 ms 212252 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 141 ms 212400 KB Output is correct
2 Correct 139 ms 212340 KB Output is correct
3 Correct 149 ms 212464 KB Output is correct
4 Correct 163 ms 212276 KB Output is correct
5 Correct 77 ms 212324 KB Output is correct
6 Correct 136 ms 212232 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 212288 KB Output is correct
2 Correct 110 ms 212344 KB Output is correct
3 Correct 119 ms 212260 KB Output is correct
4 Correct 110 ms 212436 KB Output is correct
5 Correct 78 ms 212300 KB Output is correct

Subtask #5
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 212300 KB Output is correct
2 Correct 136 ms 212344 KB Output is correct
3 Correct 134 ms 212276 KB Output is correct
4 Correct 137 ms 212292 KB Output is correct
5 Correct 131 ms 212344 KB Output is correct
6 Correct 101 ms 212276 KB Output is correct
7 Correct 79 ms 212264 KB Output is correct
8 Correct 81 ms 212268 KB Output is correct
9 Correct 108 ms 212348 KB Output is correct
10 Correct 109 ms 212300 KB Output is correct
11 Correct 81 ms 212324 KB Output is correct
12 Correct 108 ms 212224 KB Output is correct
13 Correct 109 ms 212252 KB Output is correct
14 Correct 141 ms 212400 KB Output is correct
15 Correct 139 ms 212340 KB Output is correct
16 Correct 149 ms 212464 KB Output is correct
17 Correct 163 ms 212276 KB Output is correct
18 Correct 77 ms 212324 KB Output is correct
19 Correct 136 ms 212232 KB Output is correct
20 Correct 110 ms 212288 KB Output is correct
21 Correct 110 ms 212344 KB Output is correct
22 Correct 119 ms 212260 KB Output is correct
23 Correct 110 ms 212436 KB Output is correct
24 Correct 78 ms 212300 KB Output is correct
25 Correct 130 ms 212340 KB Output is correct
26 Correct 135 ms 212256 KB Output is correct
27 Correct 124 ms 212340 KB Output is correct
28 Correct 141 ms 212324 KB Output is correct
29 Correct 145 ms 212340 KB Output is correct
30 Correct 166 ms 212428 KB Output is correct