Submission #1320827

#TimeUsernameProblemLanguageResultExecution timeMemory
1320827mirasmKitchen (BOI19_kitchen)C++20
0 / 100
227 ms21976 KiB
#include<bits/stdc++.h>
using namespace std;
#define int long long

const int N = 300 + 4;

int vt[22][N][N], vt1[22][N][N];


void fun () {  
	int n, k, m;
	cin >> n >> m >> k;
	vector<int> a(n + 1), b(m + 1);
	int s = 0;
	for (int i = 1; i <= n; i++) cin >> a[i], s += a[i];
	for (int i = 1; i <= m; i++) cin >> b[i];


	for (int i = 1; i <= n; i++) {
		if (a[i] < k) {
			cout << "Impossible";
			return;
		}	
	}
	int l = m / 2, r = (m + 1) / 2;
	
	for (int i = 0; i <= 21; i++) 
		for (int j = 0; j <= 202; j++) for (int k = 0; k <= 202; k++)  vt[i][j][k] = vt1[i][j][k] = 1e18;
	

	for (int mask = 0; mask < (1 << l); mask++) {
		int sum = 0, cnt = 0, res = 0;
		for (int i = 0; i < l; i++) {
			if (mask >> i & 1) {
				sum += min(n, b[i + 1]);	
				cnt++;
				res += b[i + 1];
			}
		}
//		cout << mask << " : " << res << ' ' << cnt << ' ' << sum << ' ';
//		for (int i = 0; i < l; i++) cout << (mask >> i & 1);
//		cout << endl;
		vt[cnt][sum][res] = min(vt[cnt][sum][res], res);
	}

	for (int mask = 0; mask < (1 << r); mask++) {
		int sum = 0, cnt = 0, res = 0;
		for (int i = 0; i < r; i++) {
			if (mask >> i & 1) {
				sum += min(n, b[i + 1 + l]);	
				cnt++;
				res += b[i + 1 + l];
			}
		}
//		cout << mask << " : " << "res " << res << " sum " << sum << " cnt " << cnt << " : ";
//		for (int i = 0; i < r; i++) cout << (mask >> i & 1);
//		cout << endl;
		vt1[cnt][sum][res] = min(vt1[cnt][sum][res], res);
	}

	for (int cnt = l; cnt >= 0; cnt--) {
		for (int sum = 200; sum >= 0; sum--) {
			for (int res = 200; res  >= 0; res--) {
				for (int mask = 0; mask < (1 << 3); mask++) {
					int a = (mask & 1), b = (mask >> 1 & 1), c = (mask >> 2 & 1);	
					vt1[cnt][sum][res] = min(vt1[cnt][sum][res], vt1[cnt + a][sum + b][res + c]);	

				}

			}
		}
	}

	for (int cnt = l; cnt >= 0; cnt--) {
		for (int sum = 200; sum >= 0; sum--) {
			for (int res = 200; res >= 0; res--) {
				for (int mask = 0; mask < (1 << 3); mask++) {
					int a = (mask & 1), b = (mask >> 1 & 1), c = (mask >> 2 & 1);	
					vt[cnt][sum][res] = min(vt[cnt][sum][res], vt[cnt + a][sum + b][res + c]);	

				}

			}
		}
	}
	
	
		
	int mx = k * n;
	int ans = 1e18;
	for (int mask = 0; mask < (1 << l); mask++) {
		int sum = 0, cnt = 0, res = 0;
		for (int i = 0; i < l; i++) {
			if (mask >> i & 1) {
				sum += min(n, b[i + 1]);	
				cnt++;
				res += b[i + 1];
			}
		}
			
		int l1 = max(0LL, k - cnt), l2 = max(0LL, k * n - sum), l3 = max(0LL, s - res);
		ans = min(ans, res + vt1[l1][l2][l3]);
//		cout << mask << " : " << l1 << ' ' << l2 << ' ' << l3 << ' ' << vt1[l1][l2][l3] << " : ";
//		for (int i = 0; i < l; i++) cout << (mask >> i & 1);
//		cout << endl;
	}

	for (int mask = 0; mask < (1 << r); mask++) {
		int sum = 0, cnt = 0, res = 0;
		for (int i = 0; i < r; i++) {
			if (mask >> i & 1) {
				sum += min(n, b[i + 1 + l]);	
				cnt++;
				res += b[i + l + 1];
			}
		}
		int l1 = max(0LL, k - cnt), l2 = max(0LL, mx - sum), l3 = max(0LL, s - res);
		ans = min(ans, res + vt[l1][l2][l3]);
	}

	if (ans == 1e18) cout << "Impossible";
	else cout << ans - s;
	
}

signed main () {
        ios_base::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
        int tt = 1;
        //cin >> tt;
        while (tt--) fun(); 
        return 0;

}



#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...