oj.uz

Submission #925917

# Submission time Handle Problem Language Result Execution time Memory
925917 2024-02-12T10:44:56 Z vjudge1 Kitchen (BOI19_kitchen) C++17
20 / 100
 438 ms 12400 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(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 11 ms 12380 KB Output is correct
2 Correct 9 ms 12264 KB Output is correct
3 Correct 9 ms 12400 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 11 ms 12380 KB Output is correct
6 Incorrect 1 ms 4444 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 12380 KB Output is correct
2 Correct 9 ms 12264 KB Output is correct
3 Correct 9 ms 12400 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 11 ms 12380 KB Output is correct
6 Incorrect 1 ms 4444 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 381 ms 12380 KB Output is correct
2 Correct 328 ms 12376 KB Output is correct
3 Correct 431 ms 12380 KB Output is correct
4 Correct 438 ms 12380 KB Output is correct
5 Correct 433 ms 12380 KB Output is correct
6 Correct 302 ms 12380 KB Output is correct

Subtask #4
0 / 21.0

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

Subtask #5
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 12380 KB Output is correct
2 Correct 9 ms 12264 KB Output is correct
3 Correct 9 ms 12400 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 11 ms 12380 KB Output is correct
6 Incorrect 1 ms 4444 KB Output isn't correct
7 Halted 0 ms 0 KB -