Submission #1296664

#TimeUsernameProblemLanguageResultExecution timeMemory
1296664Jawad_Akbar_JJKitchen (BOI19_kitchen)C++20
21 / 100
6 ms576 KiB
#include <iostream>
#include <bitset>
#include <algorithm>

using namespace std;
const int N = 305, NN = 90005; 
bitset<90005> bt[N], Bt;
int a[N], b[N];

int main(){
	int n, m, k, Ans = NN, ex = 0;
	cin>>n>>m>>k;

	for (int i=1;i<=n;i++)
		cin>>a[i];
	for (int j=1;j<=m;j++)
		cin>>b[j];

	sort(b + 1, b + m + 1);

	for (int i=1;i<=n;i++){
		if (a[i] < k)
			return cout<<"Impossible\n", 0;
		ex += a[i] - k;
	}


	Bt[0] = bt[0][0] = 1;
	for (int i=1;b[i] < n;i++)
		Bt |= Bt << b[i];

	for (int i=m;b[i] >= n;i--){
		for (int j=min(m - i + 1, k);j>=1;j--)
			bt[j] |= (bt[j-1] << (b[i] - n)) | (bt[j] << b[i]);
	}

	for (int i=k;i>=0;i--){
		for (int j=NN-1, l = 0;j>=0;j--){
			while (j >= 0 and bt[i][j] == 0)
				j--;
			while (j >= 0 and l < N and (Bt[l] == 0 or j + l < ex))
				l++;
			if (j >= 0 and l < N)
				Ans = min(Ans, j + l - ex);
		}
		Bt >>= n;
	}
	if (Ans == NN)
		cout<<"Impossible\n";
	else
		cout<<Ans<<'\n';
}
#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...