oj.uz

Submission #717009

# Submission time Handle Problem Language Result Execution time Memory
717009 2023-03-31T20:51:44 Z AmirAli_H1 Kitchen (BOI19_kitchen) C++17
100 / 100
 176 ms 219520 KB 
// In the name of Allah

#include <bits/stdc++.h>
using namespace std;

typedef long long int	ll;
typedef long double	ld;
typedef pair<int, int>	pii;
typedef pair<ll, ll>	pll;

#define all(x)		(x).begin(),(x).end()
#define len(x)		((ll) (x).size())
#define F		first
#define S		second
#define pb		push_back
#define sep             ' '
#define endl            '\n'
#define Mp		make_pair
#define debug(x)	cerr << #x << ": " <<  x << endl;
#define kill(x)		cout << x << '\n', exit(0);
#define set_dec(x)	cout << fixed << setprecision(x);
#define file_io(x,y)	freopen(x, "r", stdin); freopen(y, "w", stdout);

int n, m, k;
const int maxn = 300 + 5;
const int oo = 1e9;
int a[maxn], b[maxn];
pii dp[maxn][maxn * maxn];

pii GX(pii val, int x) {
	if (val.F >= oo) return Mp(oo, 0);
	
	if (x >= n) {
		val.F--;
	}
	else {
		val.S = x + val.S;
		val.F -= (val.S / n);
		val.S %= n;
	}
	return val;
}

pii cmp(pii a, pii b) {
	if (a.F >= oo && b.F >= oo) return Mp(oo, 0);
	else if (a.F >= oo) return b;
	else if (b.F >= oo) return a;
	
	int x = a.F * n - a.S, y = b.F * n - b.S;
	if (x < y) return a;
	else return b;
}

int main() {
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	
	cin >> n >> m >> k;
	for (int i = 1; i <= n; i++) cin >> a[i];
	for (int i = 1; i <= m; i++) cin >> b[i];
	
	int sm = 0;
	for (int i = 1; i <= n; i++) {
		if (a[i] < k) kill("Impossible");
		sm += a[i];
	}
	
	for (int i = 0; i <= m; i++) {
		dp[i][0] = Mp(k, 0);
		for (int val = 1; val < maxn * maxn; val++) {
			if (i == 0) dp[i][val] = Mp(oo, 0);
			else {
				if (val - b[i] >= 0) {
					dp[i][val] = cmp(dp[i - 1][val], GX(dp[i - 1][val - b[i]], b[i]));
				}
				else dp[i][val] = dp[i - 1][val];
			}
		}
	}
	
	for (int val = sm; val < maxn * maxn; val++) {
		if (dp[m][val].F <= 0) {
			kill(val - sm);
		}
	}
	cout << "Impossible" << endl;
	
	return 0;
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2516 KB Output is correct
2 Correct 2 ms 2516 KB Output is correct
3 Correct 2 ms 2504 KB Output is correct
4 Correct 2 ms 2388 KB Output is correct
5 Correct 2 ms 2388 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 2 ms 2516 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2516 KB Output is correct
2 Correct 2 ms 2516 KB Output is correct
3 Correct 2 ms 2504 KB Output is correct
4 Correct 2 ms 2388 KB Output is correct
5 Correct 2 ms 2388 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 2 ms 2516 KB Output is correct
9 Correct 10 ms 11976 KB Output is correct
10 Correct 9 ms 11860 KB Output is correct
11 Correct 9 ms 11980 KB Output is correct
12 Correct 9 ms 11976 KB Output is correct
13 Correct 9 ms 11940 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 146 ms 191080 KB Output is correct
2 Correct 127 ms 165584 KB Output is correct
3 Correct 171 ms 219492 KB Output is correct
4 Correct 176 ms 219520 KB Output is correct
5 Correct 174 ms 212208 KB Output is correct
6 Correct 115 ms 152500 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 30128 KB Output is correct
2 Correct 23 ms 30180 KB Output is correct
3 Correct 23 ms 30116 KB Output is correct
4 Correct 23 ms 30156 KB Output is correct
5 Correct 1 ms 212 KB Output is correct

Subtask #5
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2516 KB Output is correct
2 Correct 2 ms 2516 KB Output is correct
3 Correct 2 ms 2504 KB Output is correct
4 Correct 2 ms 2388 KB Output is correct
5 Correct 2 ms 2388 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 2 ms 2516 KB Output is correct
9 Correct 10 ms 11976 KB Output is correct
10 Correct 9 ms 11860 KB Output is correct
11 Correct 9 ms 11980 KB Output is correct
12 Correct 9 ms 11976 KB Output is correct
13 Correct 9 ms 11940 KB Output is correct
14 Correct 146 ms 191080 KB Output is correct
15 Correct 127 ms 165584 KB Output is correct
16 Correct 171 ms 219492 KB Output is correct
17 Correct 176 ms 219520 KB Output is correct
18 Correct 174 ms 212208 KB Output is correct
19 Correct 115 ms 152500 KB Output is correct
20 Correct 23 ms 30128 KB Output is correct
21 Correct 23 ms 30180 KB Output is correct
22 Correct 23 ms 30116 KB Output is correct
23 Correct 23 ms 30156 KB Output is correct
24 Correct 1 ms 212 KB Output is correct
25 Correct 115 ms 153932 KB Output is correct
26 Correct 136 ms 177912 KB Output is correct
27 Correct 92 ms 117436 KB Output is correct
28 Correct 143 ms 178644 KB Output is correct
29 Correct 141 ms 183020 KB Output is correct
30 Correct 176 ms 219424 KB Output is correct