Submission #721343

#	Time	Username	Problem	Language	Result	Execution time	Memory
721343		ParsaAp	Sparklers (JOI17_sparklers)	C++14	0 / 100	0 ms	212 KiB

sparklers

#include <bits/stdc++.h>
#define pb push_back
#define all(x) x.begin(), x.end()
#define SZ(x) ((int) x.size())
#define ld long double
using namespace std;

const int N = 4e5 + 111, INF = 1e9 + 111;
int n, k, t, X[N];
vector <ld> a[2], ps[2];
int p[2], nxt[2];
ld mn[2];
bool flag;

int g(int x) {
	return ps[x][p[x]];
}

void find_next(int x) {
	nxt[x] = -1;
	mn[x] = INF;
	int np = p[x] + 1;
	while (np < SZ(ps[x]) && (ps[x][np] < g(x) || (flag == 0 && ps[x][np] == g(x)))) {
		mn[x] = min(mn[x], ps[x][np]);
		np++;
	}
	if (np < SZ(ps[x])) nxt[x] = np;
}

bool check2() {
	for (int i = 0; i < 2; i++) {
		p[i] = nxt[i] = mn[i] = 0;
	}

	if (g(0) + g(1) < 0) return 0;
	find_next(0);
	find_next(1);
	while (nxt[0] != -1 || nxt[1] != -1) {
		if (nxt[0] != -1 && mn[0] + g(1) >= 0) {
			p[0] = nxt[0];
			find_next(0);
			continue;
		}
		if (nxt[1] != -1 && mn[1] + g(0) >= 0) {
			p[1] = nxt[1];
			find_next(1);
			continue;
		}
		return 0;
	}
	return 1;
}

bool check(int s) {
	for (int i = 0; i < 2; i++) {
		a[i].clear(), ps[i].clear();
	}
	a[0].pb(t);
	for (int i = k + 1; i < n; i++) {
		a[0].pb(-(X[i] - X[i - 1]) * 1. / (2 * s));
		a[0].pb(t);
	}
	a[1].pb(0);
	for (int i = k - 1; ~i; i--) {
		a[1].pb(-(X[i + 1] - X[i]) * 1. / (2 * s));
		a[1].pb(t);
	}
	for (int i = 0; i < 2; i++) {
		ps[i].pb(0);
		for (auto x: a[i]) {
			ps[i].pb(ps[i].back() + x);
		}	
	}

	flag = 0;
	bool ans = check2();
	reverse(all(ps[0]));
	reverse(all(ps[1]));
	flag = 1;
	ans &= check2();
	return ans;
}

void solve() {
	if (n == 1) {
		cout << 0;
		return;
	}
	int L = 0, R = 1e9 + 1;
	while (L + 1 < R) {
		int m = (L + R) >> 1;
		if (check(m)) {
			R = m;
		}
		else {
			L = m;
		}
	}
	cout << R;
}

void read() {
	cin >> n >> k >> t;
	k--;

	for (int i = 0; i < n; i++) {
		cin >> X[i];
	}
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0);

	read();
	solve();
}

• Subtask 1: 0 / 30
• Subtask 2: 0 / 20
• Subtask 3: 0 / 50