Submission #442340

#	Time	Username	Problem	Language	Result	Execution time	Memory
442340		hossain2020	Shortcut (IOI16_shortcut)	C++14	0 / 100	1 ms	332 KiB

shortcut

#include <iostream>
#include <cmath>
#include <bits/stdc++.h>
#include "shortcut.h"
using namespace std;

bool pri (int a)
{

    for (int i=2;i*i<=a;i++)
    {
        if (a%i==0)
        {
            return 0;
        }
    }
    return 1;
}
long long n,c,a[6005][6005],o=100000000,s=0,b[6005];
vector <int> x,y;
vector <pair <int ,int > > v;
long long chec (int n,vector <int> l, vector <int> d,int i,int j,int c)
{
    s=0;
    long long h;
    h=b[n-2];
    if (i<n&&j<n)
    {
        s=min(h,b[i-1]+c+b[n-2]-b[j-1]);
        h=s;
    }
    else if (i<n)
    {
        if (j-n<i)
        {
            s=min(h,b[j-n-1]+d[j-n]+c+b[n-2]-b[i-1]);
            h=s;
        }
        else s=min(h,b[i-1]+c+d[j-n]+b[n-2]-b[j-n-1]);
    }
    else s=min(h,b[i-n-1]+d[i-n]+c+d[j-n]+b[n-2]-d[j-n-1]);
    for (int x=0;x<n;x++)
    {
        if (d[x+n])
        {
            for (int y=x+1;y<n;y++)
            {
                if (d[y])
                {
                    h=d[x]+b[y-1]-b[x-1]+d[y];
                    {
                        h=min(h,d[x]+d[y]+a[x+n][i]+c+a[y+n][j]);
                    }
                    s=max(s,h);
                }
            }
        }
    }
    return s;
}
long long find_shortcut(int n,vector <int> l, vector <int> d, int c)
{
    for (int i=0;i<n-1;i++)
    {
        b[i]=l[i]+b[i-1];
    }
    for (int i=0;i<n;i++)
    {
        if (d[i])
        {
            for (int j=0;j<n-1;j++)
            {
                a[i+n][j]=d[i]+abs(b[i]-b[j]);
                a[j][i+n]=a[i+n][j];
            }
        }
    }
    for (int i=0;i<n;i++)
    {
        if (d[i])
        {
            for (int j=i+1;j<n;j++)
            {
                if (d[j])
                {
                    a[i+n][j+n]=d[i]+d[j]+b[j-1]-b[i-1];
                    a[j+n][i+n]=a[i+n][j+n];
                }
            }
        }
    }
    for (int i=0;i<n-1;i++)
    {
        for (int j=i+1;j<n;j++)
        {
            if (b[j-1]-b[i-1]>c)
            {
                o=min(o,chec(n,l,d,i,j,c));
            }
        }
    }
    for (int i=0;i<n;i++)
    {
        if (d[i])
        {
            for (int j=i+1;j<n;j++)
            {
                if (a[i+n][j+n]>c)o=min(o,chec(n,l,d,i+n,j+n,c));
                if (a[i][j+n]>c)o=min(o,chec(n,l,d,i,j+n,c));
            }
        }
    }
    return o;
}

• 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