oj.uz

Submission #859168

# Submission time Handle Problem Language Result Execution time Memory
859168 2023-10-09T21:23:49 Z NK_ Kitchen (BOI19_kitchen) C++17
100 / 100
 88 ms 100688 KB 
// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>
 
using namespace std;
 
#define nl '\n'
#define pb push_back
#define pf push_front
 
#define mp make_pair
#define f first
#define s second
#define sz(x) int(x.size())
 
template<class T> using V = vector<T>;
using pi = pair<int, int>;
using vi = V<int>;
using vpi = V<pi>;
 
using ll = long long;
using pl = pair<ll, ll>;
using vpl = V<pl>;
using vl = V<ll>;
 
using db = long double;
 
template<class T> using pq = priority_queue<T, V<T>, greater<T>>;
 
const int MOD = 1e9 + 7;
const ll INFL = ll(1e17);
const int LG = 18;

int main() {
	cin.tie(0)->sync_with_stdio(0);

	int N, M, K; cin >> N >> M >> K;

	vi A(N); for(auto& x : A) {
		cin >> x;

		if (x < K) {
			cout << "Impossible" << nl;
			exit(0-0);
		}
	}

	vi B(M); for(auto& x : B) cin >> x;

	int S = accumulate(begin(B), end(B), 0);
	int SUM = accumulate(begin(A), end(A), 0);

	V<vi> dp(M+1, vi(S+1, -MOD));

	dp[0][0] = 0;

	for(int i = 0; i < M; i++) {
		for(int x = 0; x <= S; x++) {
			int amt = min(N, B[i]);
			if ((x + B[i]) <= S) dp[i+1][x+B[i]] = max(dp[i+1][x+B[i]], dp[i][x] + amt);
			dp[i+1][x] = max(dp[i+1][x], dp[i][x]);
		}
	}

	for(int x = SUM; x <= S; x++) {
		// cout << x << " => " << dp[M][x] << nl;
		if (dp[M][x] >= N * K) {
			cout << x - SUM << nl;
			exit(0-0);
		}
	}

	cout << "Impossible" << nl;
	exit(0-0);
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 600 KB Output is correct
3 Correct 1 ms 428 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 600 KB Output is correct
3 Correct 1 ms 428 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 600 KB Output is correct
10 Correct 0 ms 604 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 0 ms 604 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 68956 KB Output is correct
2 Correct 48 ms 51544 KB Output is correct
3 Correct 49 ms 57176 KB Output is correct
4 Correct 84 ms 98396 KB Output is correct
5 Correct 82 ms 98640 KB Output is correct
6 Correct 35 ms 41564 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 604 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 0 ms 604 KB Output is correct
5 Correct 0 ms 348 KB Output is correct

Subtask #5
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 600 KB Output is correct
3 Correct 1 ms 428 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 600 KB Output is correct
10 Correct 0 ms 604 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 0 ms 604 KB Output is correct
14 Correct 57 ms 68956 KB Output is correct
15 Correct 48 ms 51544 KB Output is correct
16 Correct 49 ms 57176 KB Output is correct
17 Correct 84 ms 98396 KB Output is correct
18 Correct 82 ms 98640 KB Output is correct
19 Correct 35 ms 41564 KB Output is correct
20 Correct 0 ms 604 KB Output is correct
21 Correct 1 ms 604 KB Output is correct
22 Correct 1 ms 604 KB Output is correct
23 Correct 0 ms 604 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 43 ms 50580 KB Output is correct
26 Correct 53 ms 62300 KB Output is correct
27 Correct 16 ms 18524 KB Output is correct
28 Correct 42 ms 51548 KB Output is correct
29 Correct 58 ms 69980 KB Output is correct
30 Correct 88 ms 100688 KB Output is correct