Submission #1214909

#	Time	Username	Problem	Language	Result	Execution time	Memory
1214909		JooDdae	Sparklers (JOI17_sparklers)	C++20	100 / 100	11 ms	1608 KiB

sparklers

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

int n, k, t, a[100100];
ll p[100100];

bool solve(int mid) {
	for(int i=1;i<=n;i++) p[i] = a[i]-1ll*t*i*2*mid;
	if(p[1] < p[n]) return 0;
	
	int L = k, R = k;
	ll mx = p[k], mn = p[k];
	while(1 < L || R < n) {
		if(1 < L && p[L-1] >= mn) mx = max(mx, p[--L]);
		else if(R < n && mx >= p[R+1]) mn = min(mn, p[++R]);
		else return 0;
	}

	L = 1, R = n;
	mx = p[1], mn = p[n];
	while(L < k && k < R) {
		if(L < k && p[L+1] >= mn) mx = max(mx, p[++L]);
		else if(k < R && mx >= p[R-1]) mn = min(mn, p[--R]);
		else return 0;
	}

	return 1;
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
	cin >> n >> k >> t;
	for(int i=1;i<=n;i++) cin >> a[i];

	int l = 0, r = 1e9;
	while(l <= r) {
		int mid = (l+r)/2;
		if(solve(mid)) r = mid-1;
		else l = mid+1;
	}
	cout << l;
}

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