Submission #730809

#	Time	Username	Problem	Language	Result	Execution time	Memory
730809		gagik_2007	Kitchen (BOI19_kitchen)	C++17	100 / 100	29 ms	980 KiB

kitchen

#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: 9 / 9
• Subtask 2: 22 / 22
• Subtask 3: 20 / 20
• Subtask 4: 21 / 21
• Subtask 5: 28 / 28