Submission #932375

#	Time	Username	Problem	Language	Result	Execution time	Memory
932375		beepbeepsheep	Shortcut (IOI16_shortcut)	C++17	31 / 100	2071 ms	600 KiB

shortcut

#include "shortcut.h"
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#define ll long long
const ll maxn=505;
const ll inf=1e15;
vector<ll> adj[maxn];
ll pref[maxn];
ll suff[maxn];
ll sum[maxn];

long long find_shortcut(int n, std::vector<int> l, std::vector<int> d, int c)
{
    ll tot=0;
    for (int i=1;i<=n;i++){
        pref[i]=max<ll>(pref[i-1],d[i-1]-tot); //offsets
        if (i!=n) tot+=l[i-1];
    }
    tot=0;
    for (int i=n;i>=1;i--){
        suff[i]=max<ll>(suff[i+1],d[i-1]-tot); //offsets
        if (i!=1) tot+=l[i-2]; 
    }
    for (int i=2;i<=n;i++){
        sum[i]=sum[i-1]+l[i-2]; //distance between a and b
    }
    ll ans=inf;
    for (int i=1;i<=n;i++){
        for (int j=i+1;j<=n;j++){
            ll curr=0;
            for (int s=i;s<j;s++){
                for (int e=s+1;e<=j;e++){
                    ll ds=d[s-1],de=d[e-1]; //where is s, where is e
                    if (s==i) ds=pref[s]+sum[s]-sum[1];
                    if (e==j) de=suff[e]+sum[n]-sum[e];
                    ll dis=sum[e]-sum[s]; //direct route
                    dis=min(dis,sum[j]-sum[i]-dis+c); //alternative route
                    //if (i==3 && j==4 && s==3 && e==4) cerr<<ds<<' '<<de<<' '<<dis<<endl; 
                    curr=max(curr,ds+de+dis);
                }
            }
            for (int s=1;s<=i;s++){
                for (int e=s+1;e<=i;e++){
                    ll ds=d[s-1],de=d[e-1];
                    curr=max(curr,ds+de+sum[e]-sum[s]);
                }
            }
            for (int s=j;s<=n;s++){
                for (int e=s+1;e<=n;e++){
                    ll ds=d[s-1],de=d[e-1];
                    curr=max(curr,ds+de+sum[e]-sum[s]);
                }
            }
            ans=min(ans,curr);
        }
    }
    return ans;
}

• 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