Submission #602825

#	Time	Username	Problem	Language	Result	Execution time	Memory
602825		WongChun1234	Kitchen (BOI19_kitchen)	C++14	100 / 100	101 ms	118160 KiB

kitchen

#include<bits/stdc++.h>
using namespace std;
const int N=350,M=100050;
int n,m,k,a[N],b[N],dp[N][M],sum;
int main(){
	cin>>n>>m>>k;
	for (int i=1;i<=n;i++) {
		cin>>a[i];
		if (a[i]<k){
			cout<<"Impossible\n";
			return 0;
		}
		sum+=a[i];
	}
	for (int i=1;i<=m;i++) cin>>b[i];
	for (int i=0;i<=m;i++) for (int j=0;j<M;j++) dp[i][j]=INT_MIN;
	dp[0][0]=0;
	for (int i=1;i<=m;i++) for (int j=0;j<M;j++){
		if (j<b[i]) dp[i][j]=dp[i-1][j];
		else if (b[i]>n) dp[i][j]=max(dp[i-1][j],dp[i-1][j-b[i]]+n);
		else dp[i][j]=max(dp[i-1][j],dp[i-1][j-b[i]]+b[i]);
	}
	for (int j=sum;j<M;j++){
		if (dp[m][j]>=n*k){
			cout<<j-sum<<"\n";
			return 0;
		}
	}
	cout<<"Impossible\n";
}

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