Submission #995752

#	Time	Username	Problem	Language	Result	Execution time	Memory
995752		Tob	Sparklers (JOI17_sparklers)	C++14	100 / 100	85 ms	7456 KiB

sparklers

#include <bits/stdc++.h>

#define F first
#define S second
#define all(x) x.begin(), x.end()
#define pb push_back
#define FIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)

using namespace std;

typedef long long ll;
typedef pair <ll, ll> pii;
typedef long double ld;

const int N = 1e5 + 7;
const ll inf = 1e18;

int n, k;
ll t;
ll a[N];

int main () {
	FIO;
	cin >> n >> k >> t; k--;
	
	for (int i = 0; i < n; i++) {
		cin >> a[i];
		a[i] *= 2;
	}
	
	ll lo = 0, hi = 1e9; hi /= t;
	while (lo < hi) {
		ll mi = (lo + hi) / 2;
		vector <ll> b, c;
		vector <pii> d, e, f, g;
		for (int i = k; i; i--) b.pb(2*mi*t - (a[i]-a[i-1])/2);
		for (int i = k; i < n-1; i++) c.pb(2*mi*t - (a[i+1]-a[i])/2);
		
		ll sum = 0, mn = 0, esum = 0;
		int la = -1;
		for (int i = 0; i < k; i++) {
			sum += b[i];
			mn = min(mn, sum);
			if (sum >= 0) {
				d.pb({sum, mn});
				sum = mn = 0;
				la = i;
			}
		}
		sum = mn = 0;
		for (int i = k-1; i > la; i--) {
			sum -= b[i];
			mn = min(mn, sum);
			if (sum >= 0) {
				f.pb({sum, mn});
				esum -= sum;
				sum = mn = 0;
			}
		}
		
		sum = mn = 0; la = -1;
		for (int i = 0; i < n-k-1; i++) {
			sum += c[i];
			mn = min(mn, sum);
			if (sum >= 0) {
				e.pb({sum, mn});
				sum = mn = 0;
				la = i;
			}
		}
		sum = mn = 0;
		for (int i = n-k-2; i > la; i--) {
			sum -= c[i];
			mn = min(mn, sum);
			if (sum >= 0) {
				g.pb({sum, mn});
				esum -= sum;
				sum = mn = 0;
			}
		}
		
		ll cur = 0;
		int x = 0, y = 0, ok = 1, ds = d.size(), es = e.size();
		while (x < ds || y < es) {
			ll d1 = -inf, d2 = -inf;
			if (x < ds && cur+d[x].S >= 0) d1 = d[x].F;
			if (y < es && cur+e[y].S >= 0) d2 = e[y].F;
			if (d1 == -inf && d2 == -inf) {
				ok = 0;
				break;
			}
			else if (d1 > d2) {
				cur += d1;
				x++;
			}
			else {
				cur += d2;
				y++;
			}
		}
		
		cur += esum;
		
		d.clear(); e.clear();
		d = f; e = g;
		x = 0, y = 0, ds = d.size(), es = e.size();
		while (x < ds || y < es) {
			ll d1 = -inf, d2 = -inf;
			if (x < ds && cur+d[x].S >= 0) d1 = d[x].F;
			if (y < es && cur+e[y].S >= 0) d2 = e[y].F;
			if (d1 == -inf && d2 == -inf) {
				ok = 0;
				break;
			}
			else if (d1 > d2) {
				cur += d1;
				x++;
			}
			else {
				cur += d2;
				y++;
			}
		}
		
		if (ok) hi = mi;
		else lo = mi+1;
	}
	
	cout << lo << "\n";

	return 0;
}

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