Submission #1314151

#	Time	Username	Problem	Language	Result	Execution time	Memory
1314151		activedeltorre	Shortcut (IOI16_shortcut)	C++20	38 / 100	2095 ms	440 KiB

shortcut

#include "shortcut.h"
using namespace std;
#include <vector>
#include <iostream>
long long inf=1e17;
long long spar[100005];
long long atarna[100005];
int n;
long long dist(int a,int b,int c,int d,int add)
{
    long long minim=inf;
    minim=min(minim,spar[b]-spar[a]);
    minim=min(minim,abs(spar[b]-spar[d])+abs(spar[a]-spar[c])+add);
    return minim;
}
pair<long long,long long>eval(int i,int j,int c)
{
    long long worst=0;
    if(c>spar[j]-spar[i])
    {
        return {inf,1};
    }
    long long worts=0,dir=1;
    for(int z=1; z<=n; z++)
    {
        for(int z2=z+1; z2<=n; z2++)
        {
            long long dcurr=dist(z,z2,i,j,c)+atarna[z-1]+atarna[z2-1];
            worst=max(worst,dcurr);
            if(dcurr==worst)
            {
                if(z2>j)
                {
                    dir=1;
                }
                else
                {
                    dir=-1;
                }
            }
        }
    }
    return make_pair(worst,dir);
}
long long find_shortcut(int m, std::vector<int> l, std::vector<int> d, int c)
{
    n=m;
    for(int i=2; i<=n; i++)
    {
        spar[i]=spar[i-1]+l[i-2];
    }
    for(int i=0;i<n;i++)
    {
        atarna[i]=d[i];
    }
    long long best=0;
    for(int z=1; z<=n; z++)
    {
        for(int z2=z+1; z2<=n; z2++)
        {
            best=max(best,spar[z2]-spar[z]+d[z-1]+d[z2-1]);
        }
    }
    for(int i=1; i<=n; i++)
    {
        int st=i+1,dr=n;
        while(st<=dr)
        {
            int mij=(st+dr)/2;
            pair<long long,long long>rez=eval(i,mij,c);
            if(rez.second==1)
            {
                st=mij+1;
            }
            else
            {
                dr=mij-1;
            }
            best=min(best,rez.first);
        }
    }
    return best;
}

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: 7 / 7
• Subtask 5: 0 / 33
• Subtask 6: 0 / 22
• Subtask 7: 0 / 4
• Subtask 8: 0 / 3