Submission #724727

#	Time	Username	Problem	Language	Result	Execution time	Memory
724727		ParsaAp	Sparklers (JOI17_sparklers)	C++14	100 / 100	203 ms	13300 KiB

sparklers

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

const int N = 1e5 + 111;
const ld INF = 1e17;
int n, k;
ld T, X[N];
vector <ld> a[2], ps[2]; int mxn[2], p[2], nxt[2]; ld mn[2];

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

void go_next(int x) {
	nxt[x] = p[x] + 1;
	mn[x] = INF;
	while (nxt[x] <= mxn[x] && ps[x][nxt[x]] < ps[x][p[x]]) {
		mn[x] = min(mn[x], ps[x][nxt[x]]);
		nxt[x]++;
	}
}

void set_next(int x) {
	p[x] = nxt[x];
	go_next(x);
}

bool check2() {
	for (int i = 0; i < 2; i++) {
		p[i] = nxt[i] = mn[i] = 0;
	}
	if (g(0) + g(1) < 0) return 0;
	go_next(0);
	go_next(1);
	while (nxt[0] <= mxn[0] || nxt[1] <= mxn[1]) {
		if (nxt[0] <= mxn[0] && mn[0] + g(1) >= 0ll) {
			set_next(0);
		}
		else if (nxt[1] <= mxn[1] && mn[1] + g(0) >= 0) {
			set_next(1);
		}
		else return 0;
	}
	return 1;
}

bool check(int s) {

	a[0].clear(), a[1].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);
	}
	for (int i = k - 1; ~i; i--) {
		a[1].pb(-(X[i + 1] - X[i]) * 1. / (2 * s));
		a[1].pb(T);
	}

	ps[0].clear();
	ps[1].clear();
	for (int i = 0; i < 2; i++) {
		ps[i].pb(0);
		for (auto j: a[i]) {
			ps[i].pb(ps[i].back() + j);
		}
		mxn[i] = max_element(all(ps[i])) - ps[i].begin();
	}
	bool ans = check2();
	for (int i = 0; i < 2; i++) {
		reverse(all(ps[i]));
		mxn[i] = SZ(ps[i]) - 1 - mxn[i];
	}
	ans = ans & check2();
	return ans;
}

void solve() {
	if (X[n - 1] == 0) {
		cout << 0;
		return;
	}
	int L = 0, R = 1e9 + 1;
	while (L + 1 < R) {
		int m = (L + R) / 2;
		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: 30 / 30
• Subtask 2: 20 / 20
• Subtask 3: 50 / 50