Submission #862414

#	Time	Username	Problem	Language	Result	Execution time	Memory
862414		iskhakkutbilim	Kitchen (BOI19_kitchen)	C++17	29 / 100	26 ms	1176 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;
	}
	int sumX = accumulate(all(a), 0LL);
	if(sumX > accumulate(all(b), 0LL)){
		cout << "Impossible";
		return 0;
	}
	vector<int> B = b;
	if(goal(B, k) < n * k){
		cout << "Impossible";
		return 0;
	}

	for(int i = N*N; i >= 0; i--) can[i] = INT_MIN;
		can[0] = 0;
	for(int x : b){
		for(int i = N*N; i - x >= 0; i--){
			can[i] = max(can[i], can[i-x] + min(x, n));
		}
	}
	
	
	for(int i = sumX; i <= N*N; i++){
		if(can[i] >= n * k){
			cout << i-sumX;
			return 0;
		}
	}
//	cout << 't';
//	if(k == 1 && m > 15){
//		can[0] = 1;
//		for(int x : b){
//			for(int i = N*N; i - x >= 0; i--){
//				can[i]|= can[i-x];
//			}
//		}
//		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;
//	}
	cout << "Impossible";
	return 0;
}

Compilation message (stderr)

kitchen.cpp:29:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   29 | main(){
      | ^~~~
kitchen.cpp: In function 'int main()':
kitchen.cpp:39:6: warning: unused variable 'ans' [-Wunused-variable]
   39 |  int ans = mod;
      |      ^~~

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