제출 #652361

#제출 시각아이디문제언어결과실행 시간메모리
652361beaconmcKitchen (BOI19_kitchen)C++14
100 / 100
166 ms212464 KiB
#include <bits/stdc++.h>

typedef long long ll;
using namespace std;

#define FOR(i, x, y) for(ll i=x; i<y; i++)
#define FORNEG(i, x, y) for(ll i=x; i>y; i--)
#define fast() ios_base::sync_with_stdio(false);cin.tie(NULL)

ll n,m,k;

ll dp[301][90001];
ll meal[301];
ll chefs[301];
ll sum = 0;
ll sum2 = 0;
int main(){
	FOR(i,0,301) FOR(j,0,90001) dp[i][j] = -1;

	cin >> n >> m >> k;
	FOR(i,0,n){
		cin >> meal[i];
		sum += meal[i];
	}
	FOR(i,0,m){
		cin >> chefs[i];
		sum2 += chefs[i];
	}

	FOR(i,0,n){
		if (meal[i] < k){
			cout << "Impossible";
			return 0;
		}
	}
	ll temp = 0;
	FOR(i,0,m){
		temp += min(n, chefs[i]);
	}
	if (temp < n*k){
		cout << "Impossible";
		return 0;
	}
	if (sum > sum2){
		cout << "Impossible";
		return 0;
	}

	dp[0][0] = 0;

	FOR(i,0,m){
		FOR(j,0,90001){
			if (dp[i][j] == -1) continue;

			if (dp[i+1][j+chefs[i]] == -1){
				dp[i+1][j+chefs[i]] = min(n, chefs[i]) + dp[i][j];
			}else{
				dp[i+1][j+chefs[i]] = max(dp[i+1][j+chefs[i]], min(n, chefs[i]) + dp[i][j]);
			}
			dp[i+1][j] = max(dp[i][j], dp[i+1][j]);
		}

	}
	ll ans = 100000000000;

	FOR(i,0,301) FOR(j,0,90001){
		if (dp[i][j] == -1) continue;
		if (dp[i][j] < n*k) continue;
		if (j<sum) continue;
		ans = min(ans, j-sum);
	}
	cout << ans << endl;
}
#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...