Submission #1320867

#TimeUsernameProblemLanguageResultExecution timeMemory
1320867mirasmKitchen (BOI19_kitchen)C++20
21 / 100
84 ms136356 KiB
#include<bits/stdc++.h>
using namespace std;
#define int long long


void fun () {  
	int n, k, m;
	cin >> n >> m >> k;
	vector<int> a(n + 1), b(m + 1);
	int s = 0, s1 = 0;
	for (int i = 1; i <= n; i++) cin >> a[i], s += a[i];
	for (int i = 1; i <= m; i++) cin >> b[i], s1 += b[i];
	for (int i = 1; i <= n; i++) {
		if (a[i] < k) {
			cout << "Impossible\n";
			return;
		}	

	}
	if (k > m) {
		cout << "Impossible\n";
		return;
		
	}
	vector<vector<int>> dp(m + 1, vector<int>(s1 + 1));
	for (int i = 1; i <= m; i++) {
		for (int j = 0; j <= s1; j++) {
			if (j - b[i] >= 0) {
				dp[i][j] = dp[i - 1][j - b[i]] + min(b[i], n);
			}
			dp[i][j] = max(dp[i][j], dp[i - 1][j]);
		}
	}

	for (int i = s; i <= s1; i++) {
		if (dp[m][i] >= n * k) {
			cout << i - s << endl;
			return;
		}
	}


	cout << "Impossible";
}

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...