Submission #242165

#	Time	Username	Problem	Language	Result	Execution time	Memory
242165		oolimry	Kitchen (BOI19_kitchen)	C++14	51 / 100	372 ms	3744 KiB

kitchen

#include <bits/stdc++.h>
using namespace std;

void impossible(){ cout << "Impossible"; exit(0); }

const int MAXN = 90005;
bitset<MAXN> dpSmall;
bitset<MAXN> dpBig[305];

vector<int> small, big, smallCan;

int main(){
	int n, m, K; cin >> n >> m >> K;
	
	int sumA = 0;
	for(int i = 0;i < n;i++){
		int a; cin >> a;
		sumA += a;
		if(a < K) impossible();
	}
	
	for(int i = 0;i < m;i++){
		int b; cin >> b;
		if(b < K) small.push_back(b);
		else big.push_back(b);
	}
	
	dpSmall[0] = 1;
	for(int b : small) dpSmall |= (dpSmall << b);
	for(int i = 0;i <= MAXN;i++){
		if(dpSmall[i]) smallCan.push_back(i);
	}
	
	dpBig[0][0] = 1;
	for(int b : big){
		for(int i = (int) big.size();i >= 1;i--){
			dpBig[i] |= (dpBig[i-1] << b);
		}
	}
	
	int ans = 102345678;
	for(int no = 0;no <= m;no++){
		for(int total = 0;total <= MAXN;total++){
			if(dpBig[no][total]){
				int need = max(sumA -  total, (K-no)*n);
				auto it = lower_bound(smallCan.begin(),smallCan.end(), need);
				
				if(it == smallCan.end()) continue;
				ans = min(ans, *it + total);
			}
		}
	}
	
	if(ans == 102345678) impossible();
	cout << ans - sumA;
}

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