Submission #1366909

#TimeUsernameProblemLanguageResultExecution timeMemory
1366909ivazivaKitchen (BOI19_kitchen)C++20
31 / 100
153 ms416 KiB
#include <bits/stdc++.h>

using namespace std;

#define MAXN 305
#define int long long 

int n,m,k;
int a[MAXN],b[MAXN];
int number[MAXN];
queue<int> q;

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];
	if (m<=15)
	{
		int answer=INT_MAX;
		for (int maska=0;maska<(1<<m);maska++)
		{
			int sumb=0;for (int i=1;i<=n;i++) {number[i]=0;q.push(i);}
			for (int bit=0;bit<m;bit++)
			{
				if (!(maska&(1<<bit))) continue;
				sumb+=b[bit+1];
				for (int num=1;num<=min(n,b[bit+1]);num++) 
				{
					if (q.empty()) break;
					int node=q.front();q.pop();
					number[node]++;
					if (number[node]<a[node]) q.push(node);
				}
			}
			while (!q.empty()) q.pop();
			bool valid=true;
			for (int node=1;node<=n;node++)
			{
				if (number[node]<k) {valid=false;break;}
			}
			if (valid==true and sumb>=suma) answer=min(answer,sumb-suma);
		}
		if (answer==INT_MAX) {cout<<"Impossible"<<endl;return 0;}
		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...