제출 #840337

#제출 시각아이디문제언어결과실행 시간메모리
840337serifefedartarKitchen (BOI19_kitchen)C++17
20 / 100
97 ms106344 KiB
#include <bits/stdc++.h>
using namespace std;
 
#define debug(x) {cout << #x << ": "; for (auto it : x) cout << it << " ";cout << enl;}
#define fast ios::sync_with_stdio(0);cin.tie(0);
typedef long long ll;
#define f first
#define s second
#define MOD 998244353
#define LOGN 20
#define MAXN 305

int dp[MAXN][90005];
vector<int> meal, chef;
int main() {
	fast
	int N, M, K; 
	cin >> N >> M >> K;

	meal = vector<int>(N+1);
	chef = vector<int>(M+1);
	int sum = 0;
	for (int i = 1; i <= N; i++) {
		cin >> meal[i]; 
		sum += meal[i];
	}
	for (int i = 1; i <= M; i++)
		cin >> chef[i];

	for (int i = 0; i <= M; i++) {
		for (int total = 0; total <= 90000; total++)
			dp[i][total] = -1e8;
	}
	dp[0][0] = 0;
	
	for (int i = 1; i <= M; i++) {
		for (int total = 0; total <= 90000; total++) {
			dp[i][total] = dp[i-1][total];
			if (total - chef[i] >= 0)
				dp[i][total] = max(dp[i][total], dp[i-1][total - chef[i]] + min(chef[i], N)); 		
		}
	}

	int ans = INT_MAX;
	for (int total = sum; total <= 90000; total++) {
		if (dp[M][total] >= N * K)
			ans = min(ans, total - sum);
	}

	if (ans == INT_MAX)
		cout << "Impossible\n";
	else
		cout << ans << "\n"; 
}
#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...