Submission #71920

#	Time	Username	Problem	Language	Result	Execution time	Memory
71920		XmtosX	Shortcut (IOI16_shortcut)	C++17	0 / 100	3 ms	492 KiB

shortcut

#include <bits/stdc++.h>
#include "shortcut.h"
using namespace std;
const int N=502;
long long dis[N][N],mx[N][N],mx1[N][N];
long long find_shortcut(int n, vector<int> l, vector<int> d, int c)
{
    if (n>500)
        return 0;
    for (int i=0;i<n;i++)
    {
        mx[i][i]=d[i];
        mx1[i][i]=d[i];
    }
    for (int i=0;i<n;i++)
    {
        for (int j=i+1;j<n;j++)
        {
            dis[i][j]=dis[i][j-1]+l[j-1];
            mx[i][j]=max(mx[i][j-1],dis[i][j]+d[j]);
        }
    }
    for (int i=0;i<n;i++)
    {
        for (int j=i-1;j>=0;j--)
        {
            mx1[j][i]=max(mx1[j+1][i],dis[j][i]+d[j]);
        }
    }
    long long ans=1e18;
    for (int i=0;i<n;i++)
    {
        for (int j=i+1;j<n;j++)
        {
            long long maxx=0;
            for (int q=0;q<n;q++)
            {
                long long cur=0;
                if (q<=j)
                    cur= max(d[q]+mx[j+1][n-1]+l[j],(long long)d[j])+(min(dis[q][j],dis[i][q]+c));
                if (q>=i)
                    cur= max(cur,max((i-1>=0)?l[i-1]+d[q]+mx1[0][i-1]:0,(long long)d[i])+min(dis[i][q],dis[q][j]+c));
                if (n>2&&q>=i&&q<=j&&dis[q][j]+c<dis[i][q])
                {
                    int low=i,high=q-1,mid;
                    long long x=dis[q][j]+c;
                    while (low<=high)
                    {
                        mid= (low+high)/2;
                        if (x+dis[i][mid]<dis[mid][q])
                        {
                            cur=max(cur,x+dis[i][mid]+d[mid]+d[q]);
                            low=mid+1;
                        }
                        else
                        {
                            high=mid-1;
                            cur=max(cur,dis[mid][q]+d[q]+d[mid]);
                        }
                    }
                }
                maxx=max(maxx,cur);
            }
            ans=min(ans,maxx);
        }
    }
    return ans;
}

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