Submission #1320918

#TimeUsernameProblemLanguageResultExecution timeMemory
1320918f112Kitchen (BOI19_kitchen)C++20
21 / 100
184 ms228704 KiB
/*
cf : F112
 /)  /)  ~ ┏━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┃
( •-• )  ~ ♡ You are amazing ♡
/   づづ ~ ┗━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛
*/
#include <bits/stdc++.h>
using namespace std;

#define F first
#define S second
#define int long long
#define Ali ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)

const int N = 3e2 + 7;
const int P = 233;
const int len = 250;
const int MOD = 1e9 + 7;
const int inf = 1e18;

int gcd(int x, int y){
	while(y){
		x %= y;
		swap(x, y);
	}
	return x;
}

int binpow(int n, int k){
	if (k == 0) return 1;
	if (k % 2 == 0){
		int val = binpow(n, k / 2);
		return (val * val) % MOD;
	}
	return (n * binpow(n, k - 1)) % MOD;
}

vector < vector < int > > dp(N, vector < int > (N * N));

void abb(){
	int n, m, k;
	cin >> n >> m >> k;
	vector < int > a(n + 1);
	vector < int > b(m + 1);
	bool ok = true;
	int suma = 0, sumb = 0;
	for (int i = 1; i <= n; ++i) cin >> a[i], ok &= (a[i] >= k), suma += a[i];
	for (int i = 1; i <= m; ++i) {
		cin >> b[i]; sumb += b[i];
	}
	if (ok == false){
		cout << "Impossible\n";
		return;
	}
	for (int sum = 1; sum <= sumb; ++sum){
		for (int i = 1; i <= m; ++i){
			dp[i][sum] = dp[i - 1][sum];
			if (sum - b[i] >= 0) dp[i][sum] = max(dp[i][sum], dp[i - 1][sum - b[i]] + min(b[i], n));
		}
	}
	for (int sum = suma; sum <= sumb; ++sum){
//		cout << dp[m][sum] << " ";
		if (dp[m][sum] >= k * n){
			cout << sum - suma << "\n";
			return;
		}
	}
//	cout << "\n";
	cout << "Impossible";
}

/*
4 4 1
1 2 3 4
10 1 2 7
*/

signed main(){	
	Ali;
	int T = 1;
//	cin >> T;
	while(T--){
        abb();
	}
}
#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...