Submission #925879

#	Time	Username	Problem	Language	Result	Execution time	Memory
925879		vjudge1	Kitchen (BOI19_kitchen)	C++17	20 / 100	450 ms	12632 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<=15){
		for(int mask=0; mask<(1<<m); ++mask){
			vt<int>v;
			for(int i=0; i<m; ++i) if(mask&(1<<i)) v.pb(b[i+1]);
			sort(all(v));
			int val=0,id=1;
			for(int i=0; i<m; ++i){
				int xx=v[i]-val;
				while(id<=n && a[id]<=xx){
					xx-=a[id];
					val+=a[id];
					++id;
				}
				
			}
		}
	}
}

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