oj.uz

Submission #600386

# Submission time Handle Problem Language Result Execution time Memory
600386 2022-07-20T19:34:45 Z flappybird Uplifting Excursion (BOI22_vault) C++17
0 / 100
 25 ms 2920 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
#define MAX 303030
#define MAXS 19
#define INF 1000000000000000001
#define bb ' '
#define ln '\n'
#define Ln '\n'
#define smin(a, x) (a)=(min((a), (x)))
ll arr[MAX];
ll dp[MAX];
signed main() {
	ios::sync_with_stdio(false), cin.tie(0);
	int M;
	ll L;
	cin >> M >> L;
	int i;
	ll A, B;
	A = B = 0;
	for (i = -M; i <= M; i++) cin >> arr[i + M], (i < 0 ? A : B) += arr[i + M] * i;
	if (B < L || A > L) {
		cout << "impossible" << ln;
		return 0;
	}
	if (A + B <= L) reverse(arr, arr + M + M + 1), L *= -1, swap(A, B), A *= -1, B *= -1;
	ll cnt = 0;
	if (A + B == L) {
		for (i = -M; i <= M; i++) cnt += arr[i + M];
		cout << cnt << ln;
		return 0;
	}
	for (i = -M; i < 0; i++) cnt += arr[i + M];
	int c = 0;
	for (i = 1; i <= M; i++) {
		if (A + arr[i + M] * i > L) {
			ll x = (L - A) / i;
			if (x) c = x;
			A += x * i;
			cnt += x;
			break;
		}
		else A += arr[i + M] * i, cnt += arr[i + M];
	}
	int e = i;
	A = L - A;
	vector<tuple<ll, ll, ll>> lst;
	for (i = -M; i < 0; i++) if (arr[i + M]) lst.emplace_back(-i, 1, arr[i + M]);
	for (i = e; i <= M; i++) if (arr[i + M]) lst.emplace_back(i, -1, arr[i + M]);
	for (i = 1; i < e; i++) if (arr[i + M]) lst.emplace_back(-i, 1, arr[i + M]);
	if (c) lst.emplace_back(-e, 1, c);
	fill(dp, dp + 303000, M * 100);
	int bias = M * M + 20;
	dp[bias] = 0;
	for (auto& [w, v, mx] : lst) {
		int ww = abs(w);
		vector<priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>>> vpq(ww);
		if (w < 0) {
			for (i = M * M + 10; i >= -M * M - 10; i--) {
				int ind = (i % ww + ww) % ww;
				while (vpq[ind].size() && vpq[ind].top().second > i + M * mx) vpq[ind].pop();
				ll pv = dp[i + bias];
				if (vpq[ind].size()) dp[i + bias] = min(dp[i + bias], vpq[ind].top().first - v * (i / ww));
				vpq[ind].emplace(pv + v * (i / ww), i);
			}
		}
		else {
			for (i = -M * M - 10; i <= M * M + 10; i++) {
				int ind = (i % ww + ww) % ww;
				while (vpq[ind].size() && vpq[ind].top().second < i - M * mx) vpq[ind].pop();
				ll pv = dp[i + bias];
				if (vpq[ind].size()) dp[i + bias] = min(dp[i + bias], vpq[ind].top().first + v * (i / ww));
				vpq[ind].emplace(pv - v * (i / ww), i);
			}
		}
	}
	if (dp[bias + A] > 50 * M) cout << "impossible" << ln;
	else cout << cnt + arr[M] - dp[bias + A];
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2632 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 1 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 25 ms 2920 KB Output is correct
7 Incorrect 12 ms 2880 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2632 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 1 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 25 ms 2920 KB Output is correct
7 Incorrect 12 ms 2880 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2652 KB Output is correct
2 Correct 5 ms 2772 KB Output is correct
3 Incorrect 10 ms 2808 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2652 KB Output is correct
2 Correct 5 ms 2772 KB Output is correct
3 Incorrect 10 ms 2808 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2652 KB Output is correct
2 Correct 5 ms 2772 KB Output is correct
3 Incorrect 10 ms 2808 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2632 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 1 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 25 ms 2920 KB Output is correct
7 Incorrect 12 ms 2880 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #5-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2652 KB Output is correct
2 Correct 5 ms 2772 KB Output is correct
3 Incorrect 10 ms 2808 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2632 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 1 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 25 ms 2920 KB Output is correct
7 Incorrect 12 ms 2880 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #6-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2652 KB Output is correct
2 Correct 5 ms 2772 KB Output is correct
3 Incorrect 10 ms 2808 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2632 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 1 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 25 ms 2920 KB Output is correct
7 Incorrect 12 ms 2880 KB Output isn't correct
8 Halted 0 ms 0 KB -