Submission #1163106

#	Time	Username	Problem	Language	Result	Execution time	Memory
1163106		8pete8	Shortcut (IOI16_shortcut)	C++20	31 / 100	2093 ms	612 KiB

shortcut

#include "shortcut.h"
#include<vector>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
#define int long long
#define all(x) x.begin(),x.end()
#define pii pair<int,int>
#define pb push_back
#define f first
#define s second
const int minf=-1e18,inf=1e18;
long long find_shortcut(int32_t n, std::vector<int32_t> l, std::vector<int32_t> d, int32_t c){
    vector<int>pref(n);
    vector<pii>pmx(n+1,{0,0}),smx(n+1,{0,0});
    vector<pii>pmx2(n+1,{0,0}),smx2(n+1,{0,0});
    for(int i=1;i<n;i++)pref[i]=l[i-1]+pref[i-1];
    pmx[0]={0,-1};
    smx[n-1]={0,-1};
    for(int i=0;i<n-1;i++){
        pmx[i+1]=max(pmx[i],{d[i]-pref[i],i});
    }
    for(int i=n-1;i>0;i--){
        smx[i-1]=max(smx[i],{d[i]+pref[i],i});
    }
    auto getdist=[&](int a,int b){
        if(a>b)swap(a,b);
        return pref[b]-pref[a];
    };
    auto get=[&](int a,int b,int i,int j){
        
        return min(getdist(a,i)+getdist(b,j),getdist(a,j)+getdist(b,i));
    };
    auto getrd=[&](int a,int b,int i,int j){
        if(a<0||b<0)return minf;
        return min(getdist(a,b),c+get(a,b,i,j))+d[a]+d[b]*(!(a==b));
    };
    int ans=inf;
    for(int i=0;i<n-1;i++)for(int j=i+1;j<n;j++){
        int dia=minf;
        for(int k=0;k<n;k++){
            dia=max(dia,getrd(k,i,i,j));
            dia=max(dia,getrd(k,j,i,j));
            dia=max(dia,getrd(k,pmx[k].s,i,j));
            dia=max(dia,getrd(k,smx[k].s,i,j));
        }
        for(int k=i;k<=j;k++){
            pmx2[k]={d[k]+pref[k],k};
            if(k!=i)pmx2[k]=max(pmx2[k],pmx2[k-1]);
        }
        for(int k=j;k>=i;k--){
            smx2[k]={d[k]-pref[k],k};
            if(k!=j)smx2[k]=max(smx2[k],smx2[k+1]);
        }
        for(int k=0;k<=j;k++){
            int l=max(i,k),r=j,pos=n-1;
            while(l<=r){
                int mid=l+(r-l)/2;
                if(c+getdist(k,i)+getdist(mid,j)<getdist(k,mid))r=mid-1,pos=min(pos,mid);
                else l=mid+1;
            }
            dia=max(dia,getrd(k,smx2[pos].s,i,j));
            if(pos)dia=max(dia,getrd(k,pmx2[pos-1].s,i,j));
        }
        for(int k=j+1;k<n;k++){
            int l=i,r=min(j,k),pos=0;
            while(l<=r){
                int mid=l+(r-l)/2;
                if(c+get(k,mid,i,j)<getdist(k,mid))l=mid+1,pos=max(pos,mid);
                else r=mid-1;
            }
            dia=max(dia,getrd(k,pmx2[pos].s,i,j));
            if(pos)dia=max(dia,getrd(k,smx2[pos-1].s,i,j));
        }
        dia=max(dia,getrd(pmx[i+1].s,smx[j-1].s,i,j));
        ans=min(ans,dia);
    }
    return ans;
}

Compilation message (stderr)

shortcut.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
shortcut_c.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~

• Subtask 1: 9 / 9
• Subtask 2: 14 / 14
• Subtask 3: 8 / 8
• Subtask 4: 0 / 7
• Subtask 5: 0 / 33
• Subtask 6: 0 / 22
• Subtask 7: 0 / 4
• Subtask 8: 0 / 3