Submission #1225025

#	Time	Username	Problem	Language	Result	Execution time	Memory
1225025		emptypringlescan	Sparklers (JOI17_sparklers)	C++17	0 / 100	0 ms	328 KiB

sparklers

#include <bits/stdc++.h>
using namespace std;
int32_t main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n,k;
	long long t;
	cin >> n >> k >> t;
	long long arr[n];
	for(int i=0; i<n; i++) cin >> arr[i];
	k--;
	long long lo=0,hi=1e9+5,mid;
	while(lo<hi){
		mid=(lo+hi)/2;
		vector<long long> lft,rgt;
		for(int i=0; i<k; i++) lft.push_back(2ll*(arr[i+1]-arr[i]));
		for(int i=n-1; i>k; i--) rgt.push_back(2ll*(arr[i]-arr[i-1]));
		long long buff=t*mid;
		while(!lft.empty()||!rgt.empty()){
			if(rgt.empty()&&lft.back()<=2ll*buff){
				buff-=lft.back()/2ll;
				buff+=t*mid;
				buff=min(buff,(long long)1e15);
				lft.pop_back();
			}
			else if(lft.empty()&&rgt.back()<=2ll*buff){
				buff-=rgt.back()/2ll;
				buff+=t*mid;
				buff=min(buff,(long long)1e15);
				rgt.pop_back();
			}
			else if(lft.empty()||rgt.empty()) break;
			else if(rgt.back()<lft.back()&&rgt.back()<=2ll*buff){
				buff-=rgt.back()/2ll;
				buff+=t*mid;
				buff=min(buff,(long long)1e15);
				rgt.pop_back();
			}
			else if(lft.back()<=rgt.back()&&lft.back()<=2ll*buff){
				buff-=lft.back()/2ll;
				buff+=t*mid;
				buff=min(buff,(long long)1e15);
				lft.pop_back();
			}
			else break;
		}
		if(lft.empty()&&rgt.empty()) hi=mid;
		else lo=mid+1;
	}
	cout << (lo+1ll)/2ll;
}

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