제출 #925919

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
925919		vjudge1	Kitchen (BOI19_kitchen)	C++17	20 / 100	432 ms	12628 KiB

kitchen

#include <bits/stdc++.h>

using namespace std;

#define all(a) a.begin(),a.end()
#define pb push_back
#define vt vector
#define endl '\n'
typedef long long ll;

const ll mod=1e9+7;
const ll inf=mod;
const int N=5e6+4;

int n,m,k,a[N],b[N],used[N];

void solve(){
	cin>>n>>m>>k;
	for(int i=1; i<=n; ++i){
		cin>>a[i];
	}
	sort(a+1,a+1+n);
	for(int i=1; i<=m; ++i){
		cin>>b[i];
	}
	if(k==1){
		int sum=0;
		for(int i=1; i<=n; ++i) sum+=a[i];
		used[0]=1;
		for(int i=1; i<=m; ++i){
			for(int j=2000000; j>=b[i]; --j) used[j]=max(used[j],used[j-b[i]]);
		}
		int ans=mod;
		for(int i=sum; i<=2000000; ++i) if(used[i]) ans=min(ans,abs(i-sum));
		if(ans==mod){
			cout<<"Impossible\n";
			return;
		}
		cout<<ans<<endl;
		return;
	}
	if(m<=2){
		if(k!=2) {
			cout<<"Impossible\n";
			return;
		}
		if(m<2){
			cout<<"Impossible\n";
			return;
		}
		int sum=0;
		for(int i=1; i<=n; ++i){
			sum+=a[i];
		}
		if(n>min(b[1],b[2])){
			cout<<"Impossible\n";
			return;
		}
		if(sum>b[1]+b[2]){
			cout<<"Impossible\n";
			return;
		}
		cout<<(b[1]+b[2])-sum<<endl;
	}
}

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int tt=1;
	//	cin>>tt;
	while(tt--) {
		solve();
	}
}

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