oj.uz

Submission #823835

# Submission time Handle Problem Language Result Execution time Memory
823835 2023-08-13T08:07:06 Z vnm06 Shortcut (IOI16_shortcut) C++14
0 / 100
 1 ms 304 KB 
#include "shortcut.h"
#include<bits/stdc++.h>
using namespace std;

int N;
long long t[508], ct;
long long dst[508], calc[508];
int bst[508];

long long dist[508];
long long find_diam(int le, int ri)
{
    dist[0]=0;
    for(int i=1; i<N; i++) dist[i]=dist[i-1]+dst[i];
    if(dist[le]+ct<dist[ri])
    {
        dist[ri]=dist[le]+ct;
        for(int i=ri+1; i<N; i++)
        {
            if(dist[i]<dist[i-1]+dst[i]) break;
            dist[i]=dist[i-1]+dst[i];
        }
        for(int i=ri-1; i>=0; i--)
        {
            if(dist[i]<dist[i+1]+dst[i+1]) break;
            dist[i]=dist[i+1]+dst[i+1];
        }
    }
    else if(dist[ri]+ct<dist[le])
    {
        dist[le]=dist[ri]+ct;
        for(int i=le+1; i<N; i++)
        {
            if(dist[i]<dist[i-1]+dst[i]) break;
            dist[i]=dist[i-1]+dst[i];
        }
        for(int i=le-1; i>=0; i--)
        {
            if(dist[i]<dist[i+1]+dst[i+1]) break;
            dist[i]=dist[i+1]+dst[i+1];
        }
    }
    long long mst=0, v=0;
    for(int i=0; i<N; i++)
    {
        if(dist[i]+t[i]>mst)
        {
            mst=dist[i]+t[i];
            v=i;
        }
    }
    dist[v]=0;
    for(int i=v+1; i<N; i++) dist[i]=dist[i-1]+dst[i];
    for(int i=v-1; i>=0; i--) dist[i]=dist[i+1]+dst[i+1];
    if(dist[le]+ct<dist[ri])
    {
        dist[ri]=dist[le]+ct;
        for(int i=ri+1; i<N; i++)
        {
            if(dist[i]<dist[i-1]+dst[i]) break;
            dist[i]=dist[i-1]+dst[i];
        }
        for(int i=ri-1; i>=0; i--)
        {
            if(dist[i]<dist[i+1]+dst[i+1]) break;
            dist[i]=dist[i+1]+dst[i+1];
        }
    }
    else if(dist[ri]+ct<dist[le])
    {
        dist[le]=dist[ri]+ct;
        for(int i=le+1; i<N; i++)
        {
            if(dist[i]<dist[i-1]+dst[i]) break;
            dist[i]=dist[i-1]+dst[i];
        }
        for(int i=le-1; i>=0; i--)
        {
            if(dist[i]<dist[i+1]+dst[i+1]) break;
            dist[i]=dist[i+1]+dst[i+1];
        }
    }
    mst=0;
    for(int i=0; i<N; i++)
    {
        if(dist[i]+t[i]>mst) mst=dist[i]+t[i];
    }
    return mst+t[v];

}

long long find_shortcut(int n, std::vector<int> l, std::vector<int> d, int c)
{
    N=n;
    ct=c;
    for(int i=0; i<n; i++) t[i]=d[i];
    for(int i=1; i<n; i++) dst[i]=l[i-1];

    long long diam=find_diam(0, 0);
    for(int i=0; i<n; i++)
    {
        bst[i]=i;
        calc[i]=diam;
        for(int j=i+1; j<n; j++)
        {
            long long nd=find_diam(i, j);
            if(nd<calc[i])
            {
                calc[i]=nd;
                bst[i]=j;
            }
        }
    }
    long long mid=1e18;
    for(int i=0; i<n; i++) if(calc[i]<mid) mid=calc[i];
    return mid;
}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 304 KB n = 4, 80 is a correct answer
2 Incorrect 0 ms 212 KB n = 9, incorrect answer: jury 110 vs contestant 100
3 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 304 KB n = 4, 80 is a correct answer
2 Incorrect 0 ms 212 KB n = 9, incorrect answer: jury 110 vs contestant 100
3 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 304 KB n = 4, 80 is a correct answer
2 Incorrect 0 ms 212 KB n = 9, incorrect answer: jury 110 vs contestant 100
3 Halted 0 ms 0 KB -

Subtask #4
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 304 KB n = 4, 80 is a correct answer
2 Incorrect 0 ms 212 KB n = 9, incorrect answer: jury 110 vs contestant 100
3 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 304 KB n = 4, 80 is a correct answer
2 Incorrect 0 ms 212 KB n = 9, incorrect answer: jury 110 vs contestant 100
3 Halted 0 ms 0 KB -

Subtask #6
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 304 KB n = 4, 80 is a correct answer
2 Incorrect 0 ms 212 KB n = 9, incorrect answer: jury 110 vs contestant 100
3 Halted 0 ms 0 KB -

Subtask #7
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 304 KB n = 4, 80 is a correct answer
2 Incorrect 0 ms 212 KB n = 9, incorrect answer: jury 110 vs contestant 100
3 Halted 0 ms 0 KB -

Subtask #8
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 304 KB n = 4, 80 is a correct answer
2 Incorrect 0 ms 212 KB n = 9, incorrect answer: jury 110 vs contestant 100
3 Halted 0 ms 0 KB -