| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 128596 | jangwonyoung | Sparklers (JOI17_sparklers) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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;
}