oj.uz

Submission #730808

# Submission time Handle Problem Language Result Execution time Memory
730808 2023-04-26T13:05:22 Z gagik_2007 Kitchen (BOI19_kitchen) C++17
0 / 100
 25 ms 980 KB 
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>
#include <chrono>
#include <ctime>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <limits>
#include <iomanip>
#include <unordered_set>
#include <unordered_map>
#include <fstream>
#include <functional>
#include <random>
#include <cassert>
#include <bitset>
using namespace std;

typedef long long ll;
typedef long double ld;

#pragma GCC optimize("Ofast")

#define ff first
#define ss second

ll ttt;
const ll INF = 1e18;
const ll MOD = 1e9 + 7;
const ll N = 307;
const ll LG = 21;
ll n, m, k;
ll dp[N * N];
ll a[N];
ll b[N];

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m >> k;
	ll suma = 0, sumb = 0;
	ll mn = INF;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
		suma += a[i];
		mn = min(mn, a[i]);
	}
	for (int i = 0; i < m; i++) {
		cin >> b[i];
		sumb += b[i];
	}
	if (mn < k) {
		cout << "impossible\n";
		return 0;
	}
	for (int i = 1; i <= sumb; i++) {
		dp[i] = -INF;
	}
	for (int i = 0; i < m; i++) {
		for (int j = sumb; j >= b[i]; j--) {
			dp[j] = max(dp[j], dp[j - b[i]] + min(b[i], n));
		}
	}
	ll ans = INF;
	for (int j = suma; j <= sumb; j++) {
		//cout << j << ": " << dp[j] << endl;
		if (dp[j] >= n * k) {
			ans = min(ans, j - suma);
		}
	}
	if (ans == INF)cout << "impossible\n";
	else cout << ans << endl;
}

/// ---- - --------  ------ -------- -- - - -
/// Just a reminder. Ubuntu password is I O I
/// ---- - --------  ------ -------- -- - - -

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Incorrect 0 ms 212 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Incorrect 0 ms 212 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 844 KB Output is correct
2 Correct 12 ms 776 KB Output is correct
3 Correct 13 ms 596 KB Output is correct
4 Correct 25 ms 980 KB Output is correct
5 Incorrect 24 ms 980 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Incorrect 1 ms 324 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Incorrect 0 ms 212 KB Output isn't correct
7 Halted 0 ms 0 KB -