Submission #862390

#	Time	Username	Problem	Language	Result	Execution time	Memory
862390		iskhakkutbilim	Kitchen (BOI19_kitchen)	C++17	51 / 100	19 ms	1360 KiB

kitchen

#include <bits/stdc++.h>
using namespace std;
 
#define int long long
#define ff first
#define ss second
#define all(a) a.begin(), a.end()
 
const int mod = 1e17;
const int N = 300;
int can[300 * 300 + 10];
 
int goal(vector<int> &srt, int k){
	int cnt = 0;
	while(true){
		sort(srt.rbegin(), srt.rend());
		if(srt[k-1] <= 0){
			break;
		}
		int mn = srt[k-1];
		for(int i = 0;i < k; i++){
			srt[i]-= mn;
		}
		cnt+= mn;
	}
	return cnt;
}
 
main(){
   ios::sync_with_stdio(0);
   cin.tie(0); cout.tie(0);
   int n, m, k; 
	vector<int> a, b;
	cin >> n >> m >> k;
	a.resize(n);
	for(auto &e : a) cin >> e;
	b.resize(m);
	for(auto &e : b) cin >> e;
	int ans = mod;
	if(k > m or *min_element(all(a)) < k){
		cout << "Impossible";
		return 0;
	}
	can[0] = 1;
	for(int x : b){
		for(int i = N*N; i - x >= 0; i--){
			can[i]|= can[i-x];
		}
	}
	if(k == 1 && m > 15){
		
		int sumX = accumulate(all(a), 0LL);
		if(goal(b, k) < n){
			cout << "Impossible";
			return 0;
		}
		for(int i = sumX; i <= N*N; i++){
			if(can[i]){
				cout << i-sumX;
				return 0;
			}
		}
		cout << "Impossible";
		return 0;
	}
	for(int all = 0; all < (1<<m); all++){
		if(__builtin_popcount(all) < k) continue;
		int sumB = 0;
		int sumX = accumulate(all(a), 0LL);
		vector<int> srt;
		for(int i = 0;i < m; i++){
			if(all & (1<<i)){
				srt.push_back(b[i]);
				sumB+= b[i];
			}
		}
		if(goal(srt, k) < n){
			continue;
		}
		sumB = sumB - n * k;
		sumX = sumX - n * k;
		if(sumB >= sumX && sumX >= 0 && sumB >= 0){
			ans = min(ans, sumB - sumX);
		}
	}
	if(ans >= mod){
		cout << "Impossible";
		return 0;
	}
	cout << ans;
	return 0;
}

Compilation message (stderr)

kitchen.cpp:29:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   29 | main(){
      | ^~~~

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