oj.uz

Submission #423653

# Submission time Handle Problem Language Result Execution time Memory
423653 2021-06-11T10:57:28 Z abdzag Kitchen (BOI19_kitchen) C++17
52 / 100
 1000 ms 239048 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;
	ll sumv2 = 0;
	ll sumk = 0;
	rep(i, 0, m) {
		rrep(j, sumv2,-1) {
			rrep(o, sumk,-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);
				}
			}
		}
		sumv2 += v2[i];
		sumk++;
	}
	rep(i, sum, sumv2+1) {
		rep(j, k, sumk+1) {
			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 118 ms 238968 KB Output is correct
2 Correct 110 ms 239036 KB Output is correct
3 Correct 112 ms 238924 KB Output is correct
4 Correct 115 ms 239048 KB Output is correct
5 Correct 111 ms 239012 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 111 ms 239044 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 238968 KB Output is correct
2 Correct 110 ms 239036 KB Output is correct
3 Correct 112 ms 238924 KB Output is correct
4 Correct 115 ms 239048 KB Output is correct
5 Correct 111 ms 239012 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 111 ms 239044 KB Output is correct
9 Correct 122 ms 239044 KB Output is correct
10 Correct 115 ms 239036 KB Output is correct
11 Correct 112 ms 239044 KB Output is correct
12 Correct 110 ms 238996 KB Output is correct
13 Correct 112 ms 238992 KB Output is correct

Subtask #3
0 / 20.0

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

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 238948 KB Output is correct
2 Correct 135 ms 239004 KB Output is correct
3 Correct 113 ms 238968 KB Output is correct
4 Correct 112 ms 239012 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 118 ms 238968 KB Output is correct
2 Correct 110 ms 239036 KB Output is correct
3 Correct 112 ms 238924 KB Output is correct
4 Correct 115 ms 239048 KB Output is correct
5 Correct 111 ms 239012 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 111 ms 239044 KB Output is correct
9 Correct 122 ms 239044 KB Output is correct
10 Correct 115 ms 239036 KB Output is correct
11 Correct 112 ms 239044 KB Output is correct
12 Correct 110 ms 238996 KB Output is correct
13 Correct 112 ms 238992 KB Output is correct
14 Execution timed out 1105 ms 238976 KB Time limit exceeded
15 Halted 0 ms 0 KB -