Submission #651934

#	Time	Username	Problem	Language	Result	Execution time	Memory
651934		ymm	Kitchen (BOI19_kitchen)	C++17	100 / 100	238 ms	4812 KiB

kitchen

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx")

#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

const int N = 320;
int meal_cnt, chef_cnt, k;
int chef_time[N], meal_sum_time;
bitset<N*N> less_bs;
int nxt_less[N*N];
bitset<N*N> more_bs[N];
vector<int> less_chef;
vector<int> more_chef;

int main()
{
	cin.tie(0) -> sync_with_stdio(false);
	cin >> meal_cnt >> chef_cnt >> k;
	Loop (i,0,meal_cnt) {
		int x;
		cin >> x;
		if (x < k) {
			cout << "Impossible\n";
			return 0;
		}
		meal_sum_time += x;
	}
	Loop (i,0,chef_cnt) {
		int x;
		cin >> x;
		(x <= meal_cnt? less_chef: more_chef).push_back(x);
	}
	less_bs[0] = 1;
	for (int x : less_chef)
		less_bs |= less_bs << x;
	nxt_less[N*N-1] = N*N;
	LoopR (i,0,N*N-1)
		nxt_less[i] = less_bs[i]? i: nxt_less[i+1];
	more_bs[0][0] = 1;
	for (int x : more_chef) {
		LoopR (i,1,N)
			more_bs[i] |= more_bs[i-1] << x;
	}
	int ans = N*N;
	Loop (cnt_more,0,N) Loop (time_more,0,N*N) {
		if (!more_bs[cnt_more][time_more])
			continue;
		int req = 0;
		req = max(req, meal_sum_time - (int)time_more);
		req = max(req, (int)(k-cnt_more)*meal_cnt);
		if (req >= N*N || nxt_less[req] == N*N)
			continue;
		ans = min(ans, nxt_less[req] + (int)time_more - meal_sum_time);
	}
	if (ans == N*N)
		cout << "Impossible\n";
	else
		cout << ans << '\n';
}

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