| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 784909 | YassirSalama | Shortcut (IOI16_shortcut) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "shortcut.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll MAXN=5100;
const ll INF=1e9+10;
#define dbg(x) cout<<"[ "<<#x<<" ] : "<<x<<endl;
#define F first
#define S second
#define all(v) v.begin(),v.end()
vector<long long> pref(MAXN+1,0);
vector<int> D;
pair<long long,long long> tree[4*MAXN];
void build(int node,int l,int r){
if(l==r){
tree[node].F=pref[l]+D[l];
tree[node].S=l;
return;
}
int mid=(l+r)/2;
build(node<<1,l,mid);
build(node<<1|1,mid+1,r);
tree[node].F=max(tree[node<<1].F,tree[node<<1|1].F);
if(tree[node].F==tree[node<<1].F) tree[node].S=tree[node<<1].S;
else tree[node].S=tree[node<<1|1].S;
}
pair<int,int> query(int node,int l,int r,int ql,int qr){
if(ql<=l&&r<=qr){
return {tree[node].F,tree[node].S};
}
int mid=(l+r)/2;
int ans=0;
int index=0;
if(ql<=mid){
pair<int,int> x=query(node<<1,l,mid,ql,qr);
if(ans<x.F){
ans=x.F;
index=x.S;
}
}
if(qr>mid){
pair<int,int> x=query(node<<1|1,mid+1,r,ql,qr);
if(ans<x.F) ans=x.F,index=x.S;
}
return {ans,index};
}
long long find_shortcut(int n, vector<int> l, vector<int> d, int c)
{
D=d;
if(n==2){
if(c<l[0])
return (long long)d[0]+c+(long long)d[1];
return (ll)d[0]+(ll)l[0]+(ll)d[1];
}
for(long long i=0;i<n-1;i++){
pref[i+1]=pref[i]+l[i];
}
build(1,0,n-1);
vector<long long> left(MAXN+1,0);
vector<long long> right(MAXN+1,0);
left[0]=(ll)d[0];
long long first_node=0;
for(long long i=1;i<n;i++){
if(d[i]>left[i-1]+l[i-1]) first_node=i;
left[i]=max(left[i-1]+l[i-1],(ll)d[i]);
}
long long last_node=n-1;
right[n-1]=d[n-1];
for(long long i=n-2;i>=0;i--){
if(d[i]>right[i+1]+l[i]&&i!=first_node) last_node=i;
right[i]=max(right[i+1]+l[i],(ll)d[i]);
}
vector<long long> nodes;//nodes in the diameter
long long diameter=left[first_node]+right[first_node];
for(long long i=0;i<=n-1;i++){
for(long long j=i+1;j<=n-1;j++){
long long express=left[i]+c+right[j];
long long newdiameter=0;
for(long long k=0;k<=n-1;k++){
newdiameter=max({newdiameter,
min(
(ll)abs(pref[j]-pref[k])+right[j]+(d[k]==right[j]&&k==j?0LL:d[k]) ,
(ll)right[j]+(ll)c+(ll)abs(pref[i]-pref[k])+(d[k]==right[j]&&k==j?0LL:d[k])
)
});
}
for(long long k=n-1;k>=0;k--){
newdiameter=max({newdiameter,
min(
(ll)abs(pref[k]-pref[i])+left[i]+(d[k]==left[i]&&k==i?0:d[k]),
(ll)left[i]+c+abs(pref[j]-pref[k])+(d[k]==left[i]&&k==i?0:d[k])
)
});
if(i==2&&j==8&&k==0){
}
}
long long ans=0;
for(int x=i;x<=j;x++){
int y=query(1,0,n-1,x,j);
if(y==x) continue;
ans=max(ans,y-pref[x]+d[x]);
}
if(ans==336){
}
diameter=min(max(a,express),diameter);
}
}
return diameter;
}
int main()
{
int n, c;
assert(2 == scanf("%d%d", &n, &c));
std::vector<int> l(n - 1);
std::vector<int> d(n);
for (int i = 0; i < n - 1; i++)
assert(1 == scanf("%d", &l[i]));
for (int i = 0; i < n; i++)
assert(1 == scanf("%d", &d[i]));
long long t = find_shortcut(n, l, d, c);
printf("%lld\n", t);
return 0;
}