Submission #1294583

#	Time	Username	Problem	Language	Result	Execution time	Memory
1294583		kian2009	Sparklers (JOI17_sparklers)	C++20	0 / 100	1 ms	576 KiB

sparklers

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;

const int MAXN = 1e5 + 10;

ll n, k, t, x[MAXN];
vector<ll> h1, h2, h;

void input() {
	cin >> n >> k >> t;
	--k;
	for (int i = 0; i < n; i++)
		cin >> x[i];
}

void calcH() {
	for (int i = 0; i < k; i++)
		h1.push_back(x[i + 1] - x[i]);
	for (int i = n - 1; i > k; i--)
		h2.push_back(x[i] - x[i - 1]);
	for (int i = 0; i < n - 1; i++) {
		if (h1.empty()) {
			h.push_back(h2.back());
			h2.pop_back();	
		}
		else if (h2.empty()) {
			h.push_back(h1.back());
			h1.pop_back();	
		}
		else {
			if (h1.back() < h2.back()) {
				h.push_back(h1.back());
				h1.pop_back();	
			}
			else {
				h.push_back(h2.back());
				h2.pop_back();	
			}
		}
	}
}

bool check(ll s) {
	ld r = t;
	for (auto x : h) {
		ld d = ((ld) x) / (2 * s);
		if (r < d)
			return false;
		r = (r - d + t);
	}
	return true;
}

ll findAns() {
	ll l = -1, r = 1e9 + 1;
	while (r - l > 1) {
		ll mid = (l + r) / 2;
		if (check(mid))
			r = mid;
		else
			l = mid;
	}
	return r;
}

int main() {
	ios::sync_with_stdio(false); cin.tie(0);
	input();
	if (n == 1)
		cout << 0 << endl;
	else {
		calcH();
		cout << findAns() << endl;
	}
	return 0;
}

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