oj.uz

Submission #925919

# Submission time Handle Problem Language Result Execution time Memory
925919 2024-02-12T10:46:49 Z vjudge1 Kitchen (BOI19_kitchen) C++17
20 / 100
 432 ms 12628 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<=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.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 Correct 1 ms 4444 KB Output is correct
5 Correct 8 ms 12380 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Incorrect 1 ms 4444 KB Output isn't correct
8 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 Correct 1 ms 4444 KB Output is correct
5 Correct 8 ms 12380 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Incorrect 1 ms 4444 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 377 ms 12380 KB Output is correct
2 Correct 326 ms 12380 KB Output is correct
3 Correct 430 ms 12376 KB Output is correct
4 Correct 432 ms 12624 KB Output is correct
5 Correct 418 ms 12628 KB Output is correct
6 Correct 299 ms 12376 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 Correct 1 ms 4444 KB Output is correct
5 Correct 8 ms 12380 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Incorrect 1 ms 4444 KB Output isn't correct
8 Halted 0 ms 0 KB -