oj.uz

Submission #925879

# Submission time Handle Problem Language Result Execution time Memory
925879 2024-02-12T10:20:43 Z vjudge1 Kitchen (BOI19_kitchen) C++17
20 / 100
 450 ms 12632 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12376 KB Output is correct
2 Correct 8 ms 12380 KB Output is correct
3 Correct 8 ms 12380 KB Output is correct
4 Incorrect 1 ms 4444 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12376 KB Output is correct
2 Correct 8 ms 12380 KB Output is correct
3 Correct 8 ms 12380 KB Output is correct
4 Incorrect 1 ms 4444 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 376 ms 12376 KB Output is correct
2 Correct 327 ms 12376 KB Output is correct
3 Correct 435 ms 12380 KB Output is correct
4 Correct 450 ms 12624 KB Output is correct
5 Correct 422 ms 12632 KB Output is correct
6 Correct 311 ms 12380 KB Output is correct

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 4444 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12376 KB Output is correct
2 Correct 8 ms 12380 KB Output is correct
3 Correct 8 ms 12380 KB Output is correct
4 Incorrect 1 ms 4444 KB Output isn't correct
5 Halted 0 ms 0 KB -