제출 #798722

#제출 시각아이디문제언어결과실행 시간메모리
798722vjudge1Kitchen (BOI19_kitchen)C++17
100 / 100
190 ms116940 KiB
#include <bits/stdc++.h>
using namespace std;

int N, M, K;
int totA;
int A[310], B[310];
int dp[310][310*310];

int f(int m, int t) {
	if (m==0) {
		if (t==0) return 0;
		else return -1e9;
	}
	int& res = dp[m][t];
	if (res != -1) return res;
	res = max(f(m-1,t), f(m-1,t-B[m])+min(N,B[m]));
//	cout << m << " " << t << " " << res << endl;
	return res;
}


int main() {
	cin >> N >> M >> K;
	for(int i=1; i<=N; i++) {
		cin >> A[i];
		totA += A[i];
		if (A[i] < K) {
			cout << "Impossible" << endl;
			return 0;
		}
	}
	for(int i=1; i<=M; i++) {
		cin >> B[i];
	}
	memset(dp, -1, sizeof(dp));
	for(int i=totA; i<=300*300; i++) {
//		cout << i << " " << f(N,i) << endl;
		if (f(M, i) >= N*K) {
			cout << i-totA << endl;
			return 0;
		}
	}
	cout << "Impossible" << 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...