제출 #840343

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
840343		serifefedartar	Kitchen (BOI19_kitchen)	C++17	100 / 100	81 ms	106344 KiB

kitchen

#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];
		if (meal[i] < K) {
			cout << "Impossible\n";
			return 0; 
		}
	}
	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"; 
}

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