Submission #1367423

#TimeUsernameProblemLanguageResultExecution timeMemory
1367423ivazivaKitchen (BOI19_kitchen)C++20
100 / 100
9 ms1088 KiB
#include <bits/stdc++.h>

using namespace std;

#define MAXN 301
#define int long long 

int n,m,k;
int a[MAXN],b[MAXN];
int dp[MAXN*MAXN];

int32_t main()
{
	cin>>n>>m>>k;
	for (int i=1;i<=n;i++) cin>>a[i];
	for (int i=1;i<=m;i++) cin>>b[i];
	int suma=0;for (int i=1;i<=n;i++) suma+=a[i];
	int sumb=0;for (int i=1;i<=m;i++) sumb+=b[i];
	if (k>m) {cout<<"Impossible"<<endl;return 0;}
	for (int i=1;i<=n;i++)
	{
		if (a[i]<k) {cout<<"Impossible"<<endl;return 0;}
	}
	dp[0]=0;for (int i=1;i<=sumb;i++) dp[i]=-INT_MAX;
	for (int i=1;i<=m;i++)
	{
		for (int val=sumb-b[i];val>=0;val--)
		{
			if (dp[val]==-INT_MAX) continue;
			dp[val+b[i]]=max(dp[val+b[i]],dp[val]+min(b[i],n));
		}
	}
	int answer=INT_MAX;
	for (int val=suma;val<=sumb;val++)
	{
		if (dp[val]>=n*k) {answer=val-suma;break;}
	}
	if (answer==INT_MAX) cout<<"Impossible"<<endl;
	else cout<<answer<<endl;
	return 0;
}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...