oj.uz

Submission #237912

# Submission time Handle Problem Language Result Execution time Memory
237912 2020-06-09T09:38:55 Z grt Kitchen (BOI19_kitchen) C++17
100 / 100
 366 ms 101240 KB 
#include <bits/stdc++.h>
#define PB push_back
#define ST first
#define ND second
#define _ ios_base::sync_with_stdio(0); cin.tie(0);
//mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

using namespace std;

using ll = long long;
using pi = pair<int,int>;
using vi = vector<int>;

const int nax = 300 + 1, INF = 1e9;
int n,m,k;
int s,s2;
int t[nax];
int dp[nax * nax][nax];

int main() {_
	cin >> n >> m >> k;
	bool ok = 1;
	for(int a,i = 1; i <= n; ++i) {
		cin >> a;
		if(a < k) ok = 0;
		s += a;
	}
	for(int i = 1; i <= m; ++i) {
		cin >> t[i];
		s2 += t[i];
	}
	if(!ok) {
		cout << "Impossible";
		return 0;
	}
	for(int i = 0; i <= s2; ++i) {
		dp[i][0] = -INF;
	}
	dp[0][0] = 0;
	for(int i = 1; i <= m; ++i) {
		for(int j = 0; j <= s2; ++j) {
			dp[j][i] = max(dp[j][i-1], (j >= t[i] ? (dp[j - t[i]][i-1] + min(t[i], n)) : -INF));
		}
	}
	int ans = INF;
	for(int i = s; i <= s2; ++i) {
		if(dp[i][m] >= k * n) {
			ans = i;
			break;
		}
	}
	if(ans == INF) cout << "Impossible";
	else {
		cout << ans - s;
	}
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 640 KB Output is correct
2 Correct 5 ms 640 KB Output is correct
3 Correct 5 ms 768 KB Output is correct
4 Correct 5 ms 1024 KB Output is correct
5 Correct 5 ms 1024 KB Output is correct
6 Correct 4 ms 384 KB Output is correct
7 Correct 4 ms 384 KB Output is correct
8 Correct 5 ms 640 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 640 KB Output is correct
2 Correct 5 ms 640 KB Output is correct
3 Correct 5 ms 768 KB Output is correct
4 Correct 5 ms 1024 KB Output is correct
5 Correct 5 ms 1024 KB Output is correct
6 Correct 4 ms 384 KB Output is correct
7 Correct 4 ms 384 KB Output is correct
8 Correct 5 ms 640 KB Output is correct
9 Correct 8 ms 3968 KB Output is correct
10 Correct 6 ms 3712 KB Output is correct
11 Correct 6 ms 640 KB Output is correct
12 Correct 5 ms 512 KB Output is correct
13 Correct 7 ms 4992 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 173 ms 77952 KB Output is correct
2 Correct 119 ms 67448 KB Output is correct
3 Correct 116 ms 56952 KB Output is correct
4 Correct 277 ms 97528 KB Output is correct
5 Correct 366 ms 101240 KB Output is correct
6 Correct 103 ms 59392 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1920 KB Output is correct
2 Correct 6 ms 1408 KB Output is correct
3 Correct 6 ms 1792 KB Output is correct
4 Correct 6 ms 2048 KB Output is correct
5 Correct 4 ms 384 KB Output is correct

Subtask #5
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 640 KB Output is correct
2 Correct 5 ms 640 KB Output is correct
3 Correct 5 ms 768 KB Output is correct
4 Correct 5 ms 1024 KB Output is correct
5 Correct 5 ms 1024 KB Output is correct
6 Correct 4 ms 384 KB Output is correct
7 Correct 4 ms 384 KB Output is correct
8 Correct 5 ms 640 KB Output is correct
9 Correct 8 ms 3968 KB Output is correct
10 Correct 6 ms 3712 KB Output is correct
11 Correct 6 ms 640 KB Output is correct
12 Correct 5 ms 512 KB Output is correct
13 Correct 7 ms 4992 KB Output is correct
14 Correct 173 ms 77952 KB Output is correct
15 Correct 119 ms 67448 KB Output is correct
16 Correct 116 ms 56952 KB Output is correct
17 Correct 277 ms 97528 KB Output is correct
18 Correct 366 ms 101240 KB Output is correct
19 Correct 103 ms 59392 KB Output is correct
20 Correct 6 ms 1920 KB Output is correct
21 Correct 6 ms 1408 KB Output is correct
22 Correct 6 ms 1792 KB Output is correct
23 Correct 6 ms 2048 KB Output is correct
24 Correct 4 ms 384 KB Output is correct
25 Correct 152 ms 70776 KB Output is correct
26 Correct 155 ms 75912 KB Output is correct
27 Correct 41 ms 34048 KB Output is correct
28 Correct 137 ms 61952 KB Output is correct
29 Correct 183 ms 82944 KB Output is correct
30 Correct 307 ms 99320 KB Output is correct