oj.uz

Submission #242164

# Submission time Handle Problem Language Result Execution time Memory
242164 2020-06-27T03:55:32 Z oolimry Kitchen (BOI19_kitchen) C++14
0 / 100
 5 ms 256 KB 
#include <bits/stdc++.h>
using namespace std;

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

const int MAXN = 30;
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
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 256 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 256 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 256 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 256 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 28.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 256 KB Output isn't correct
2 Halted 0 ms 0 KB -