Submission #749465

#	Time	Username	Problem	Language	Result	Execution time	Memory
749465		TheOpChicken	Sparklers (JOI17_sparklers)	C++17	0 / 100	0 ms	212 KiB

sparklers

#include <iostream>
using namespace std;

const long long maxN = 1e5 + 5, inf = 1e9;
long long arr[maxN];

int main(){
	long long n, k, t;
	cin >> n >> k >> t;

	for (int i = 0; i < n; i++) cin >> arr[i];

	k--;
	long long l = 1, r = inf, ans = inf;

	while(l <= r){
		long long mid = (l+r)/2, left_margin = 0, right_margin = 0;

		if (mid*t >= inf){
			ans = mid;
			r = mid-1;
			continue;
		}

		int left = k, right = k, pos = 1;
		while(pos){
			pos = 0;
			if(left){
				long long last = arr[k] - 2*(k-(left-1))*mid*t - left_margin;
				if (last <= arr[left-1]){
					left_margin = 0;
					right_margin = arr[left-1] - last;
					left--;
					pos = 1;
				}
			}
			if (right < n-1){
				long long last = arr[k] + 2*(right+1 - k)*mid*t + right_margin;
				if (last >= arr[right+1]){
					right_margin = 0;
					left_margin = last - arr[right+1];
					right++;
					pos = 1;
				}
			}
		}

		if (left == 0 && right == n-1){
			ans = mid;
			r = mid-1;
		}
		else l = mid+1;
	}

	cout << ans << endl;
}

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