oj.uz

Submission #600308

# Submission time Handle Problem Language Result Execution time Memory
600308 2022-07-20T17:31:13 Z flappybird Uplifting Excursion (BOI22_vault) C++17
0 / 100
 4 ms 1516 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];
int 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 = 1;
			A += x * i;
			cnt += x;
			break;
		}
		else A += arr[i + M] * i, cnt += arr[i + M];
	}
	int e = i;
	A = L - A;
	vector<pii> v;
	for (i = -M; i < 0; i++) if (arr[i + M]) v.emplace_back(-i, 1);
	for (i = e; i <= M; i++) if (arr[i + M]) v.emplace_back(i, -1);
	if (!c) e--;
	for (i = 1; i <= e; i++) if (arr[i + M]) v.emplace_back(-i, 1);
	fill(dp, dp + 303000, M * 100);
	int bias = M * M + 20;
	dp[bias] = 0;
	for (auto& [w, v] : v) {
		if (w < 0) for (i = -M * M - 10 - w; i <= M * M + 10; i++) dp[i + w + bias] = min(dp[i + w + bias], dp[i + bias] + v);
		else for (i = M * M + 10 - w; i >= -M * M - 10; i--) dp[i + w + bias] = min(dp[i + w + bias], dp[i + bias] + v);
	}
	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 1 ms 1492 KB Output is correct
2 Correct 1 ms 1492 KB Output is correct
3 Correct 1 ms 1492 KB Output is correct
4 Correct 1 ms 1492 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 4 ms 1492 KB Output is correct
7 Correct 2 ms 1492 KB Output is correct
8 Correct 3 ms 1492 KB Output is correct
9 Correct 4 ms 1516 KB Output is correct
10 Incorrect 1 ms 1492 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1492 KB Output is correct
2 Correct 1 ms 1492 KB Output is correct
3 Correct 1 ms 1492 KB Output is correct
4 Correct 1 ms 1492 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 4 ms 1492 KB Output is correct
7 Correct 2 ms 1492 KB Output is correct
8 Correct 3 ms 1492 KB Output is correct
9 Correct 4 ms 1516 KB Output is correct
10 Incorrect 1 ms 1492 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1492 KB Output is correct
2 Correct 1 ms 1492 KB Output is correct
3 Correct 1 ms 1492 KB Output is correct
4 Correct 1 ms 1492 KB Output is correct
5 Correct 2 ms 1492 KB Output is correct
6 Correct 2 ms 1492 KB Output is correct
7 Incorrect 1 ms 1492 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1492 KB Output is correct
2 Correct 1 ms 1492 KB Output is correct
3 Correct 1 ms 1492 KB Output is correct
4 Correct 1 ms 1492 KB Output is correct
5 Correct 2 ms 1492 KB Output is correct
6 Correct 2 ms 1492 KB Output is correct
7 Incorrect 1 ms 1492 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1492 KB Output is correct
2 Correct 1 ms 1492 KB Output is correct
3 Correct 1 ms 1492 KB Output is correct
4 Correct 1 ms 1492 KB Output is correct
5 Correct 2 ms 1492 KB Output is correct
6 Correct 2 ms 1492 KB Output is correct
7 Incorrect 1 ms 1492 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1492 KB Output is correct
2 Correct 1 ms 1492 KB Output is correct
3 Correct 1 ms 1492 KB Output is correct
4 Correct 1 ms 1492 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 4 ms 1492 KB Output is correct
7 Correct 2 ms 1492 KB Output is correct
8 Correct 3 ms 1492 KB Output is correct
9 Correct 4 ms 1516 KB Output is correct
10 Incorrect 1 ms 1492 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #5-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1492 KB Output is correct
2 Correct 1 ms 1492 KB Output is correct
3 Correct 1 ms 1492 KB Output is correct
4 Correct 1 ms 1492 KB Output is correct
5 Correct 2 ms 1492 KB Output is correct
6 Correct 2 ms 1492 KB Output is correct
7 Incorrect 1 ms 1492 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #5-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1492 KB Output is correct
2 Correct 1 ms 1492 KB Output is correct
3 Correct 1 ms 1492 KB Output is correct
4 Correct 1 ms 1492 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 4 ms 1492 KB Output is correct
7 Correct 2 ms 1492 KB Output is correct
8 Correct 3 ms 1492 KB Output is correct
9 Correct 4 ms 1516 KB Output is correct
10 Incorrect 1 ms 1492 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #6-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1492 KB Output is correct
2 Correct 1 ms 1492 KB Output is correct
3 Correct 1 ms 1492 KB Output is correct
4 Correct 1 ms 1492 KB Output is correct
5 Correct 2 ms 1492 KB Output is correct
6 Correct 2 ms 1492 KB Output is correct
7 Incorrect 1 ms 1492 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #6-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1492 KB Output is correct
2 Correct 1 ms 1492 KB Output is correct
3 Correct 1 ms 1492 KB Output is correct
4 Correct 1 ms 1492 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 4 ms 1492 KB Output is correct
7 Correct 2 ms 1492 KB Output is correct
8 Correct 3 ms 1492 KB Output is correct
9 Correct 4 ms 1516 KB Output is correct
10 Incorrect 1 ms 1492 KB Output isn't correct
11 Halted 0 ms 0 KB -