| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 113165 | baluteshih | Shortcut (IOI16_shortcut) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define pb push_back
#define jizz ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define F first
#define S second
#define ET cout << "\n"
#define MP make_pair
#define MEM(i,j) memset(i,j,sizeof i)
#define ALL(v) v.begin(),v.end()
#define DB(a,s,e) {for(int i=s;i<e;++i) cout << a[i] << " ";ET;}
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const ll INF=1e18;
ll find_shortcut(int n, int l[], int d[], int c)
{
ll mx=-INF,ans=0;
vector<ll> sl(n,0),ldp(n,0),rdp(n,0),lf(n,0),rf(n,0),nd(n,0);
for(int i=0;i<n;++i)
nd[i]=d[i];
for(int i=1;i<n;++i)
sl[i]=sl[i-1]+l[i-1];
for(int i=0;i<n;++i)
ldp[i]=max((ll)d[i],sl[i]+mx),mx=max(mx,ldp[i]-sl[i]);
for(int i=1;i<n;++i)
lf[i]=max(lf[i-1],ldp[i-1]+d[i]+sl[i]-sl[i-1]);
for(int i=n-1;i>=0;--i)
rdp[i]=max((ll)d[i],mx-sl[i]),mx=max(mx,rdp[i]+sl[i]);
for(int i=n-2;i>=0;--i)
rf[i]=max(rf[i+1],rdp[i+1]+d[i]+sl[i+1]-sl[i]);
ans=lf[n-1];
for(int i=0;i<n;++i)
for(int j=i+1;j<n;++j)
{
ll tmp=max(lf[i],rf[j]),mx2=-INF,cir=sl[j]-sl[i]+c;
nd[i]=ldp[i],nd[j]=rdp[j];
deque<int> dq;
for(int k=i+1;k<=j;++k)
{
while(dq.size()&&nd[dq.back()]-sl[dq.back()]<=nd[k-1]-sl[k-1])
dq.pop_back();
dq.pb(k-1);
while(dq.size()&&(sl[k]-sl[dq[0]])*2>=cir)
mx2=max(mx2,sl[dq[0]]+nd[dq[0]]),dq.pop_front();
if(dq.size()) tmp=max(tmp,sl[k]+nd[k]+nd[dq[0]]-sl[dq[0]]);
tmp=max(tmp,mx2+cir-sl[k]+nd[k]);
}
ans=min(tmp,ans),nd[i]=d[i],nd[j]=d[j];
}
return ans;
}