Submission #1294672

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

sparklers

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

typedef long long ll;

const int MAXN = 1e5 + 10;

ll n, k, t, x[MAXN], pt1, pt2, pt3, pt4, sum1, sum2, sum;
vector<ll> h1, h2;

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

void setup(ll s) {
	pt1 = pt2 = pt3 = pt4 = sum = sum1 = sum2 = 0;
	h1.clear();
	h2.clear();
	for (int i = k; i > 0; i--)
		h1.push_back(x[i] - x[i - 1] - s);
	for (int i = k + 1; i < n; i++)
		h2.push_back(x[i] - x[i - 1] - s);
}

void move() {
	while (pt3 < h1.size() && (sum >= sum1 && sum1 > 0)) {
		sum1 += h1[pt3];
		pt3++;
	}
	while (pt4 < h2.size() && (sum >= sum2 && sum2 > 0)) {
		sum2 += h2[pt4];
		pt4++;	
	}
}

bool check(ll s) {
	setup(s);
	while (pt1 < h1.size() || pt2 < h2.size()) {
		move();
		if (pt1 != h1.size() && (sum >= sum1 && sum1 < 0)) {
			sum -= sum1;
			sum1 = 0;
			pt1 = pt3;
			continue;	
		}
		if (pt2 != h2.size() && (sum >= sum2 && sum2 < 0)) {
			sum -= sum2;
			sum2 = 0;
			pt2 = pt4;
			continue;
		}
		if ((pt1 != h1.size() && sum < sum1) || (pt2 != h2.size() && sum < sum2))
			return false;
		if (pt1 == h1.size()) {
			if (sum < h2[pt2])
				return false;
			sum -= h2[pt2];
			pt2++;	
		}
		else if (pt2 == h2.size()) {
			if (sum < h1[pt1])
				return false;
			sum -= h1[pt1];
			pt1++;	
		}
		else {
			if (sum < min(h1[pt1], h2[pt2]))
				return false;
			if (h1[pt1] < h2[pt2]) {
				sum -= h1[pt1];
				pt1++;
			}
			else {
				sum -= h2[pt2];
				pt2++;	
			}
		}
	}
	return true;
}

ll findAns() {
	ll l = -1, r = x[n - 1];
	while (r - l > 1) {
		ll mid = (l + r) / 2;
		if (check(2 * mid * t))
			r = mid;
		else
			l = mid;
	}
	return r;
}

int main() {
	ios::sync_with_stdio(false); cin.tie(0);
	input();
	cout << findAns() << endl;
	return 0;
}

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