Submission #401347

#	Time	Username	Problem	Language	Result	Execution time	Memory
401347		idontreallyknow	Kitchen (BOI19_kitchen)	C++17	100 / 100	356 ms	115360 KiB

kitchen

#include <bits/stdc++.h>
using namespace std;
template <typename T> bool chkmax(T &x,T y){return x<y?x=y,true:false;}
template <typename T> bool chkmin(T &x,T y){return x>y?x=y,true:false;}
const int mx = 305, inf = 1e9+5;
int a[mx], b[mx], good[mx*mx], mi[mx][mx*mx], tot;
bitset<mx*mx> bs[mx];
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n,m,k;
	cin >> n >> m >> k;
	bool ok = true;
	for (int q = 1; q <= n; q++) {
		cin >> a[q];
		tot += a[q];
		if (a[q] < k) ok = false;
	}
	vector<int> small, large;
	for (int q = 1; q <= m; q++) {
		cin >> b[q];
		if (b[q] < n) small.push_back(b[q]);
		else large.push_back(b[q]);
	}
	if (!ok) {
		cout << "Impossible\n";
		return 0;
	}
	good[0] = 1;
	for (int q : small) {
		for (int w = mx*mx-1; w >= 0; w--) if (w-q >= 0) good[w] |= good[w-q];
	}
	bs[0][0] = 1;
	for (int q : large) {
		for (int w = mx-1; w >= 1; w--) {
			bs[w] |= (bs[w-1]<<q);
		}
	}
	for (int q = mx-1; q >= 0; q--) {
		for (int w = mx*mx-1; w >= 0; w--) {
			mi[q][w] = inf;
			if (bs[q][w]) mi[q][w] = w;
			if (q < mx-1) chkmin(mi[q][w], mi[q+1][w]);
			if (w < mx*mx-1) chkmin(mi[q][w], mi[q][w+1]);
		}
	}
	int ans = inf;
	for (int q = 0; q < mx*mx; q++) {
		if (!good[q]) continue;
		int f = (q >= n*k ? 0 : (n*k-q+n-1)/n), g = max(0,tot-q);
		chkmin(ans, mi[f][g]+q);
	}
	if (ans == inf) cout << "Impossible\n";
	else cout << ans-tot << '\n';
	return 0;
}

• Subtask 1: 9 / 9
• Subtask 2: 22 / 22
• Subtask 3: 20 / 20
• Subtask 4: 21 / 21
• Subtask 5: 28 / 28