Submission #493118

#	Time	Username	Problem	Language	Result	Execution time	Memory
493118		Haruto810198	Kitchen (BOI19_kitchen)	C++17	100 / 100	156 ms	150320 KiB

kitchen

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define double long double

#define FOR(i, l, r, d) for(int i=(l); i<=(r); i+=(d))
#define szof(x) ((int)(x).size())

#define vi vector<int>
#define pii pair<int, int>

#define F first
#define S second

#define pb push_back
#define eb emplace_back
#define mkp make_pair

const int INF = 1000000007;
const int LNF = INF*INF;
const int MOD = 1000000007;
const int mod = 998244353;
const double eps = 1e-12;

//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")

const int MAX = 302;

int n, m, lim; // meals, chefs, required chefs
int md, mw; // dian chefs, weak chefs
int meal[MAX], chef[MAX], meal_sum, dian_sum;
int chef_dian[MAX], chef_weak[MAX];

int dp_dian[MAX*MAX];
bool dp_weak[MAX*MAX];
int suf[MAX][MAX*MAX];
int res;

signed main(){
	
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	cin>>n>>m>>lim;
	FOR(i, 1, n, 1){
		cin>>meal[i];
		meal_sum += meal[i];
	}
	FOR(i, 1, m, 1){
		cin>>chef[i];
		if(chef[i] >= n) chef_dian[++md] = chef[i], dian_sum += chef[i];
		else chef_weak[++mw] = chef[i];
	}
	
	// meal[i] >= lim
	FOR(i, 1, n, 1){
		if(meal[i] < lim){
			cout<<"Impossible"<<'\n';
			return 0;
		}
	}
	
	// dp_dian
	dp_dian[0] = 0;
	FOR(i, 1, md*MAX, 1){
		dp_dian[i] = -INF;
	}

	FOR(i, 1, md, 1){
		for(int j=i*MAX; j>=chef_dian[i]; j--){
			dp_dian[j] = max(dp_dian[j], dp_dian[j - chef_dian[i]] + 1);
		}
	}
	
	// dp_weak
	dp_weak[0] = 1;
	FOR(i, 1, mw, 1){
		for(int j=i*MAX; j>=chef_weak[i]; j--){
			if(dp_weak[j - chef_weak[i]]) dp_weak[j] = 1;
		}
	}

	// suf
	for(int i=md; i>=0; i--){
		for(int j=md*MAX; j>=0; j--){
			suf[i][j] = INF;
		}
	}
	
	FOR(i, 0, md*MAX, 1){
		if(dp_dian[i] >= 0) suf[ dp_dian[i] ][i] = i;
	}

	for(int i=md; i>=0; i--){
		for(int j=md*MAX; j>=0; j--){
			if(i < md) suf[i][j] = min(suf[i][j], suf[i+1][j]);
			if(j < md*MAX) suf[i][j] = min(suf[i][j], suf[i][j+1]);
		}
	}
	/*
	cerr<<"ok"<<endl;
	cerr<<"dp_dian : "<<endl;
	FOR(i, 0, 10, 1){
		if(dp_dian[i] < -INF / 2) cerr<<"- ";
		else cerr<<dp_dian[i]<<" ";
	}
	cerr<<endl;

	cerr<<"suf : "<<endl;
	FOR(i, 0, md, 1){
		FOR(j, 0, 10, 1){
			if(suf[i][j] >= INF) cerr<<"- ";
			else cerr<<suf[i][j]<<" ";
		}
		cerr<<endl;
	}
	cerr<<endl;

	cerr<<"dp_weak : "<<endl;
	FOR(i, 0, 10, 1){
		cerr<<dp_weak[i]<<" ";
	}
	cerr<<endl;
	*/
	res = INF;

	// weak chefs + dian chefs	
	FOR(j, 0, meal_sum - 1, 1){
		if(dp_weak[j] == 0) continue;
		int req_chefs = max((int)0, lim - (j / n)); // required dian chefs
		int req_sum = meal_sum - j; // required sum of time
		//cerr<<"j = "<<j<<" ["<<req_chefs<<"]["<<req_sum<<"] "<<endl;
		if(req_chefs > md or req_sum > dian_sum) continue;
		res = min(res, j + suf[req_chefs][req_sum] - meal_sum);
	}
	
	// weak chefs only
	FOR(j, meal_sum, mw*MAX, 1){
		if(dp_weak[j]) res = min(res, j - meal_sum);
	}

	if(res < INF / 2) cout<<res<<'\n';
	else cout<<"Impossible"<<'\n';

	return 0;

}

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