oj.uz

Submission #651933

# Submission time Handle Problem Language Result Execution time Memory
651933 2022-10-20T14:47:19 Z ymm Kitchen (BOI19_kitchen) C++17
0 / 100
 54 ms 4348 KB 
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx")

#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

const int N = 320;
int meal_cnt, chef_cnt, k;
int chef_time[N], meal_sum_time;
bitset<N*N> less_bs;
int nxt_less[N];
bitset<N*N> more_bs[N];
vector<int> less_chef;
vector<int> more_chef;

int main()
{
	cin.tie(0) -> sync_with_stdio(false);
	cin >> meal_cnt >> chef_cnt >> k;
	Loop (i,0,meal_cnt) {
		int x;
		cin >> x;
		if (x < k) {
			cout << "Impossible\n";
			return 0;
		}
		meal_sum_time += x;
	}
	Loop (i,0,chef_cnt) {
		int x;
		cin >> x;
		(x <= meal_cnt? less_chef: more_chef).push_back(x);
	}
	less_bs[0] = 1;
	for (int x : less_chef)
		less_bs |= less_bs << x;
	nxt_less[N-1] = N*N;
	LoopR (i,0,N-1)
		nxt_less[i] = less_bs[i]? i: nxt_less[i+1];
	more_bs[0][0] = 1;
	for (int x : more_chef) {
		LoopR (i,1,N)
			more_bs[i] |= more_bs[i-1] << x;
	}
	int ans = N*N;
	Loop (cnt_more,0,N) Loop (time_more,0,N*N) {
		if (!more_bs[cnt_more][time_more])
			continue;
		int req = 0;
		req = max(req, meal_sum_time - (int)time_more);
		req = max(req, (int)(k-cnt_more)*meal_cnt);
		if (req >= N*N || nxt_less[req] == N*N)
			continue;
		ans = min(ans, nxt_less[req] + (int)time_more - meal_sum_time);
	}
	if (ans == N*N)
		cout << "Impossible\n";
	else
		cout << ans << '\n';
}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 4308 KB Output is correct
2 Correct 31 ms 4348 KB Output is correct
3 Correct 32 ms 4252 KB Output is correct
4 Correct 30 ms 4308 KB Output is correct
5 Incorrect 31 ms 340 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 4308 KB Output is correct
2 Correct 31 ms 4348 KB Output is correct
3 Correct 32 ms 4252 KB Output is correct
4 Correct 30 ms 4308 KB Output is correct
5 Incorrect 31 ms 340 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 468 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

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

Subtask #5
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 4308 KB Output is correct
2 Correct 31 ms 4348 KB Output is correct
3 Correct 32 ms 4252 KB Output is correct
4 Correct 30 ms 4308 KB Output is correct
5 Incorrect 31 ms 340 KB Output isn't correct
6 Halted 0 ms 0 KB -