oj.uz

Submission #423638

# Submission time Handle Problem Language Result Execution time Memory
423638 2021-06-11T10:45:45 Z abdzag Kitchen (BOI19_kitchen) C++17
52 / 100
 1000 ms 239172 KB 
#include<bits/stdc++.h>
#include<unordered_map>
#define rep(i,a,b) for(int i=int(a);i<int(b);i++)
#define rrep(i,a,b) for(int i=int(a);i>int(b);i--)
#define trav(a,v) for(auto& a: v)
#define sz(v) v.size()
#define all(v) v.begin(),v.end()
#define vi vector<int>

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
const long long inf = 1e15;

using namespace std;
int main() {
	cin.sync_with_stdio(false);
	ll n, m, k;
	cin >> n >> m >> k;
	vector<ll> v(n);
	vector<ll> v2(m);
	rep(i, 0, n) {
		cin >> v[i];
		if (v[i] < k) {
			cout << "Impossible" << endl;
			return 0;
		}
	}
	rep(i, 0, m)cin >> v2[i];
	ll sum = 0;
	rep(i, 0, n)sum += v[i];
	sort(all(v2), greater<>());
	vector < vector<ll>>dp0(1e5,vector<ll>(301,-inf));
	dp0[0][0] = 0;;
	ll ans = inf;
	rep(i, 0, m) {
		rrep(j, 300 * 300,-1) {
			rrep(o, 300,-1) {
				if (dp0[j][o] != -inf) {
					ll change=0;
					if (o + 1 > k)change = v2[i];
					else if (v2[i] < n)change = -n + v2[i];
					dp0[j + v2[i]][o + 1] = max(dp0[j + v2[i]][o + 1], dp0[j][o] + change);
				}
			}
		}
	}
	rep(i, sum, 300 * 300 + 1) {
		rep(j, k, 301) {
			if (dp0[i][j] >= 0) {
				ll ii = i;
				ans = min(ans, ii);
			}
		}
	}
	if (ans == inf)cout << "Impossible" << endl;
	else cout << ans - sum << endl;
	return 0;
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 185 ms 239020 KB Output is correct
2 Correct 187 ms 238980 KB Output is correct
3 Correct 201 ms 239056 KB Output is correct
4 Correct 188 ms 239060 KB Output is correct
5 Correct 191 ms 239044 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 1 ms 316 KB Output is correct
8 Correct 187 ms 239056 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 185 ms 239020 KB Output is correct
2 Correct 187 ms 238980 KB Output is correct
3 Correct 201 ms 239056 KB Output is correct
4 Correct 188 ms 239060 KB Output is correct
5 Correct 191 ms 239044 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 1 ms 316 KB Output is correct
8 Correct 187 ms 239056 KB Output is correct
9 Correct 511 ms 239052 KB Output is correct
10 Correct 454 ms 239048 KB Output is correct
11 Correct 457 ms 239172 KB Output is correct
12 Correct 459 ms 239044 KB Output is correct
13 Correct 474 ms 239060 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1089 ms 239044 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 962 ms 239112 KB Output is correct
2 Correct 997 ms 239056 KB Output is correct
3 Correct 989 ms 239052 KB Output is correct
4 Correct 982 ms 239172 KB Output is correct
5 Correct 0 ms 204 KB Output is correct

Subtask #5
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 185 ms 239020 KB Output is correct
2 Correct 187 ms 238980 KB Output is correct
3 Correct 201 ms 239056 KB Output is correct
4 Correct 188 ms 239060 KB Output is correct
5 Correct 191 ms 239044 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 1 ms 316 KB Output is correct
8 Correct 187 ms 239056 KB Output is correct
9 Correct 511 ms 239052 KB Output is correct
10 Correct 454 ms 239048 KB Output is correct
11 Correct 457 ms 239172 KB Output is correct
12 Correct 459 ms 239044 KB Output is correct
13 Correct 474 ms 239060 KB Output is correct
14 Execution timed out 1089 ms 239044 KB Time limit exceeded
15 Halted 0 ms 0 KB -