제출 #128598

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
128598		jangwonyoung	Sparklers (JOI17_sparklers)	C++14	0 / 100	2 ms	376 KiB

sparklers

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,k;
ll t;
ll x[100001];
stack<ll>sl,sr;
bool solve(ll s){
	while(!sl.empty()) sl.pop();
	while(!sr.empty()) sr.pop();
	for(int i=1; i<k ;i++) sl.push(x[i+1]-x[i]);
	for(int i=n; i>k ;i--) sr.push(x[i]-x[i-1]);
	ll cnt=0;
	for(int i=1; i<n ;i++){
		ll cur=s;
		while(cur>0){
			if(!sl.empty() && (sr.empty() || sl.top()<=sr.top()) ){
				if(sl.top()<=cur){
					cur-=sl.top();
					cnt++;
					sl.pop();
				}
				else{
					sl.top()-=cur;cur=0;
				}
			}
			else if(!sr.empty() && (sl.empty() || sr.top()<=sl.top())){
				if(sr.top()<=cur){
					cur-=sr.top();
					cnt++;
					sr.pop();
				}
				else{
					sr.top()-=cur;cur=0;
				}
			}
			else cur=0;
		}
		if(cnt==0) return false;
		cnt--;
	}
	return true;
}
int main(){
	ios::sync_with_stdio(false);
	cin >> n >> k >> t;
	for(int i=1; i<=n ;i++){
		cin >> x[i];
	}
	ll l=0,r=1e9;
	while(l!=r){
		ll mid=(l+r)/2;
		if(solve(mid*t*2)) r=mid;
		else l=mid+1;
	}
	cout << l << endl;
}

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