| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 128596 | jangwonyoung | Sparklers (JOI17_sparklers) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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.top().empty() && (sr.top().empty() || sl.top()<=sr.top()) ){
if(sl.top()<=cur){
cur-=sl.top();
cnt++;
sl.pop();
}
else{
sl.top()-=cur;cur=0;
}
}
else if(!sr.top().empty() && (sl.top().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;
}