Submission #386141

#	Time	Username	Problem	Language	Result	Execution time	Memory
386141		pit4h	Sparklers (JOI17_sparklers)	C++14	0 / 100	1 ms	392 KiB

sparklers

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

bool solve(int n, int k, ll t, vector<ll> x) {
	int l = k, r = k, L=k, R = k;	
	for(int i=0; i<n; ++i) {
		while(l > 0 && (R-l+1) * t - (x[R] - x[l-1]) / 2 >= 0LL) {
			l--;
			if((k-l) * t + x[l] / 2 > (k-L) * t + x[L] / 2) {
				L = l;
			}
		}
		while(r < n-1 && (r-L+1) * t - (x[r+1] - x[L]) / 2 >= 0LL) {
			r++;
			if((r-k) * t - x[r] / 2 > (R-k) * t - x[R] / 2) {
				R = r;
			}
		}
	}
	return l==0 && r==n-1;
}
int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int n, k;
	ll t;
	cin>>n>>k>>t;
	k--;
	t *= 2LL;
	vector<ll> x(n);
	for(int i=0; i<n; ++i) {
		cin>>x[i];
		x[i] *= 2LL;
	}

	ll lo = 0, hi = 1e10 / t + 1;
	while(lo<=hi) {
		ll mid = (lo+hi)/2LL;
		if(solve(n, k, t*mid, x)) {
			hi = mid-1;
		}
		else {
			lo = mid+1;
		}
	}
	cout<<hi+1<<'\n';
}

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