Submission #386141

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
386141	2021-04-05T18:41:11 Z	pit4h	Sparklers (JOI17_sparklers)	C++14	0 / 100	1 ms	392 KB

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.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	1 ms	380 KB	Output is correct
4	Correct	1 ms	384 KB	Output is correct
5	Correct	1 ms	364 KB	Output is correct
6	Correct	1 ms	364 KB	Output is correct
7	Correct	1 ms	392 KB	Output is correct
8	Correct	1 ms	364 KB	Output is correct
9	Correct	1 ms	364 KB	Output is correct
10	Correct	1 ms	364 KB	Output is correct
11	Correct	1 ms	364 KB	Output is correct
12	Incorrect	1 ms	364 KB	Output isn't correct
13	Halted	0 ms	0 KB	-

Subtask #2

0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	1 ms	380 KB	Output is correct
4	Correct	1 ms	384 KB	Output is correct
5	Correct	1 ms	364 KB	Output is correct
6	Correct	1 ms	364 KB	Output is correct
7	Correct	1 ms	392 KB	Output is correct
8	Correct	1 ms	364 KB	Output is correct
9	Correct	1 ms	364 KB	Output is correct
10	Correct	1 ms	364 KB	Output is correct
11	Correct	1 ms	364 KB	Output is correct
12	Incorrect	1 ms	364 KB	Output isn't correct
13	Halted	0 ms	0 KB	-

Subtask #3

0 / 50.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	1 ms	380 KB	Output is correct
4	Correct	1 ms	384 KB	Output is correct
5	Correct	1 ms	364 KB	Output is correct
6	Correct	1 ms	364 KB	Output is correct
7	Correct	1 ms	392 KB	Output is correct
8	Correct	1 ms	364 KB	Output is correct
9	Correct	1 ms	364 KB	Output is correct
10	Correct	1 ms	364 KB	Output is correct
11	Correct	1 ms	364 KB	Output is correct
12	Incorrect	1 ms	364 KB	Output isn't correct
13	Halted	0 ms	0 KB	-