Submission #1320838

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

const int N = 1600+ 4;

int vt[42][N][N], vt1[42][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 <= 41; i++) 
		for (int j = 0; j < N; j++) for (int k = 0; k < N; k++)  vt[i][j][k] = vt1[i][j][k] = 1e9;
	

	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];
			}
		}
		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];
//			}
//		}
//		vt1[cnt][sum][res] = min(vt1[cnt][sum][res], res);
//	}
//
//	for (int cnt = 40; cnt >= 0; cnt--) {
//		for (int sum = N - 2; sum >= 0; sum--) {
//			for (int res = N - 2; res  >= 0; res--) {
//				vt1[cnt][sum][res] = min(vt1[cnt][sum][res], vt1[cnt + 1][sum + 0][res + 0]);	
//				vt1[cnt][sum][res] = min(vt1[cnt][sum][res], vt1[cnt + 0][sum + 1][res + 0]);	
//				vt1[cnt][sum][res] = min(vt1[cnt][sum][res], vt1[cnt + 1][sum + 1][res + 0]);	
//				vt1[cnt][sum][res] = min(vt1[cnt][sum][res], vt1[cnt + 0][sum + 0][res + 1]);	
//				vt1[cnt][sum][res] = min(vt1[cnt][sum][res], vt1[cnt + 1][sum + 0][res + 1]);	
//				vt1[cnt][sum][res] = min(vt1[cnt][sum][res], vt1[cnt + 0][sum + 1][res + 1]);	
//				vt1[cnt][sum][res] = min(vt1[cnt][sum][res], vt1[cnt + 1][sum + 1][res + 1]);	
//
//
//			}
//		}
//	}
//
//	for (int cnt = 40; cnt >= 0; cnt--) {
//		for (int sum = N - 2; sum >= 0; sum--) {
//			for (int res = N - 2; res >= 0; res--) {
//				vt[cnt][sum][res] = min(vt[cnt][sum][res], vt[cnt + 1][sum + 0][res + 0]);	
//				vt[cnt][sum][res] = min(vt[cnt][sum][res], vt[cnt + 0][sum + 1][res + 0]);	
//				vt[cnt][sum][res] = min(vt[cnt][sum][res], vt[cnt + 1][sum + 1][res + 0]);	
//				vt[cnt][sum][res] = min(vt[cnt][sum][res], vt[cnt + 0][sum + 0][res + 1]);	
//				vt[cnt][sum][res] = min(vt[cnt][sum][res], vt[cnt + 1][sum + 0][res + 1]);	
//				vt[cnt][sum][res] = min(vt[cnt][sum][res], vt[cnt + 0][sum + 1][res + 1]);	
//				vt[cnt][sum][res] = min(vt[cnt][sum][res], vt[cnt + 1][sum + 1][res + 1]);	
//
//
//			}
//		}
//	}
//	
//	
//		
//	int mx = k * n;
//	int ans = 1e9;
//	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(0, k - cnt), l2 = max(0, k * n - sum), l3 = max(0, s - res);
//		ans = min(ans, res + vt1[l1][l2][l3]);
//	}
//
//	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(0, k - cnt), l2 = max(0, mx - sum), l3 = max(0, s - res);
//		ans = min(ans, res + vt[l1][l2][l3]);
//	}
//
//	if (ans == 1e9) 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...