oj.uz

Submission #331688

# Submission time Handle Problem Language Result Execution time Memory
331688 2020-11-29T14:39:14 Z soroush Kitchen (BOI19_kitchen) C++14
100 / 100
 65 ms 876 KB 
//*
//#pragma GCC optimize("O2")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
//#pragma GCC target("avx,avx2,sse,sse2,fma,tune=native")
//*/
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef pair<int  ,int > pii;
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
const ll maxn  = 1e5;
const ll mod =1e9+7;
const ld PI = acos((ld)-1);
 
#define pb push_back
#define endl '\n'
#define dokme(x) cout << x , exit(0)
#define migmig ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define ms(x , y) memset(x , y , sizeof x)
ll pw(ll a, ll b, ll md = mod){ll res = 1;while(b){if(b&1){res=(a*res)%md;}a=(a*a)%md;b>>=1;}return(res);}
 
int n , m , k;
int a[maxn];
int b[maxn];
int suma = 0 , sumb = 0;

int dp[maxn];

int32_t main(){
    migmig;
	cin >> n >> m >> k;
	for(int i = 0 ; i < n ; i ++)	
		cin >> a[i], suma+=a[i];
	for(int i = 0 ; i < m ; i ++)
		cin >> b[i], sumb+=b[i];
	sort(a , a + n);
	sort(b , b + m);
	if(m < k)dokme("Impossible");
	if(*min_element(a , a + n) < k)dokme("Impossible");
	if(suma > sumb)dokme("Impossible");
	ms(dp, -1);
	dp[0] = 0;
	for(int i = 0 ; i < m ; i ++)
		for(int j = sumb ; j >= 0 ; j --)
			if(dp[j] != -1) dp[j + b[i]] = max(dp[j + b[i]] , dp[j] + min(b[i] , n));
	for(int i = suma ; i <= sumb ; i ++ )
		if(dp[i] >= n*k)dokme(i - suma);
	cout << "Impossible";
    return(0);
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 748 KB Output is correct
2 Correct 1 ms 768 KB Output is correct
3 Correct 1 ms 748 KB Output is correct
4 Correct 1 ms 748 KB Output is correct
5 Correct 1 ms 748 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 748 KB Output is correct
2 Correct 1 ms 768 KB Output is correct
3 Correct 1 ms 748 KB Output is correct
4 Correct 1 ms 748 KB Output is correct
5 Correct 1 ms 748 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 748 KB Output is correct
10 Correct 1 ms 748 KB Output is correct
11 Correct 1 ms 748 KB Output is correct
12 Correct 1 ms 748 KB Output is correct
13 Correct 1 ms 748 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 748 KB Output is correct
2 Correct 23 ms 748 KB Output is correct
3 Correct 29 ms 748 KB Output is correct
4 Correct 58 ms 808 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 13 ms 748 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 748 KB Output is correct
2 Correct 1 ms 748 KB Output is correct
3 Correct 1 ms 620 KB Output is correct
4 Correct 1 ms 748 KB Output is correct
5 Correct 1 ms 364 KB Output is correct

Subtask #5
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 748 KB Output is correct
2 Correct 1 ms 768 KB Output is correct
3 Correct 1 ms 748 KB Output is correct
4 Correct 1 ms 748 KB Output is correct
5 Correct 1 ms 748 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 748 KB Output is correct
10 Correct 1 ms 748 KB Output is correct
11 Correct 1 ms 748 KB Output is correct
12 Correct 1 ms 748 KB Output is correct
13 Correct 1 ms 748 KB Output is correct
14 Correct 16 ms 748 KB Output is correct
15 Correct 23 ms 748 KB Output is correct
16 Correct 29 ms 748 KB Output is correct
17 Correct 58 ms 808 KB Output is correct
18 Correct 1 ms 364 KB Output is correct
19 Correct 13 ms 748 KB Output is correct
20 Correct 1 ms 748 KB Output is correct
21 Correct 1 ms 748 KB Output is correct
22 Correct 1 ms 620 KB Output is correct
23 Correct 1 ms 748 KB Output is correct
24 Correct 1 ms 364 KB Output is correct
25 Correct 12 ms 748 KB Output is correct
26 Correct 23 ms 876 KB Output is correct
27 Correct 11 ms 748 KB Output is correct
28 Correct 30 ms 768 KB Output is correct
29 Correct 45 ms 876 KB Output is correct
30 Correct 65 ms 748 KB Output is correct