Submission #1366990

#TimeUsernameProblemLanguageResultExecution timeMemory
1366990ivazivaKitchen (BOI19_kitchen)C++20
0 / 100
1 ms344 KiB
#include <bits/stdc++.h>

using namespace std;

#define MAXN 45
#define int long long 

int n,m,k;
int a[MAXN],b[MAXN];
vector<int> grt;
bool dp[MAXN*MAXN];
bool newdp[MAXN][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];
	for (int i=1;i<=n;i++)
	{
		if (a[i]<k) {cout<<"Impossible"<<endl;return 0;}
	}
	int suma=0;for (int i=1;i<=n;i++) suma+=a[i];
	grt.push_back(0);int sumb=0;for (int i=1;i<=m;i++) sumb+=b[i];
	dp[0]=true;for (int val=1;val<=sumb;val++) dp[val]=false;
	for (int i=1;i<=m;i++)
	{
		if (b[i]>=n) {grt.push_back(b[i]);continue;}
		for (int val=sumb;val>=0;val--)
		{
			if (val+b[i]>=MAXN*MAXN) continue;
			if (dp[val]==true) dp[val+b[i]]=true;
		}
	}
	for (int number=0;number<(int)grt.size();number++)
	{
		for (int val=0;val<=sumb;val++) newdp[number][val]=false;
	}
	newdp[0][0]=true;
	for (int pos=1;pos<(int)grt.size();pos++)
	{
		for (int number=(int)grt.size()-1;number>=1;number--)
		{
			for (int val=sumb;val>=0;val--)
			{
				if (val+grt[pos]>=MAXN*MAXN) continue;
				if (newdp[number-1][val]==true) newdp[number][val+grt[pos]]=true;
			}
		}
	}
	int answer=INT_MAX;
	for (int val=0;val<=sumb;val++)
	{
		if (dp[val]==false) continue;
		int num_greater=k-(val+n-1)/n;
		if (num_greater<0) num_greater=0;
		else if (num_greater>=(int)grt.size()) continue;
		int fali=max((long long)0,suma-val);
		for (int value=fali;value<=sumb;value++)
		{
			if (newdp[num_greater][value]) {answer=min(answer,val+value-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...