제출 #652361

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
652361		beaconmc	Kitchen (BOI19_kitchen)	C++14	100 / 100	166 ms	212464 KiB

kitchen

#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;
}

• Subtask 1: 9 / 9
• Subtask 2: 22 / 22
• Subtask 3: 20 / 20
• Subtask 4: 21 / 21
• Subtask 5: 28 / 28