oj.uz

Submission #44846

# Submission time Handle Problem Language Result Execution time Memory
44846 2018-04-08T08:37:42 Z RayaBurong25_1 Shortcut (IOI16_shortcut) C++17
0 / 100
 2 ms 376 KB 
#include "shortcut.h"
#include <stdio.h>
#define INF 1e18
int N;
long long C;
long long QL[3005];
long long MaxD[3005][3005];
int MD[3005][3005];
long long min(long long a, long long b)
{
    return (a < b)?a:b;
}
long long max(long long a, long long b)
{
    return (a > b)?a:b;
}
long long calc(int a, int b)
{
    int mn = a, md, mx = b;
    while (1)
    {
        if (mx - mn <= 1)
        {
            if (QL[mn] - QL[a] > C + QL[b] - QL[mn])
                break;
            else if (QL[mx] - QL[a] > C + QL[b] - QL[mx])
            {
                mn = mx;
                break;
            }
            else
                return INF;
        }
        md = (mn + mx)/2;
        if (QL[md] - QL[a] > C + QL[b] - QL[md])
            mx = md;
        else
            mn = md;
    }
    // printf("mn %d\n", mn);
    long long Mx = MaxD[0][0];
    int id = 0;
    Mx = max(Mx, MaxD[0][mn - 1]);
    if (Mx == MaxD[0][mn - 1]) id = MD[0][mn - 1];
    Mx = max(Mx, QL[a] + C + MaxD[b][N - 1]);
    if (Mx == QL[a] + C + MaxD[b][N - 1]) id = MD[b][N - 1];
    Mx = max(Mx, QL[a] + C + MaxD[b][b]);
    if (Mx == QL[a] + C + MaxD[b][b]) id = MD[b][b];
    Mx = max(Mx, QL[a] + C + MaxD[b][mn]);
    if (Mx == QL[a] + C + MaxD[b][mn]) id = MD[b][mn];
    // printf("id%d\n", id);

    //id = furthest from 0
    int found;
    if (a <= id && id <= b)
    {
        Mx = 0;
        mn = a;
        mx = id;
        found = 0;
        while (1)
        {
            if (mx - mn <= 1)
            {
                if (QL[id] - QL[mx] > QL[b] - QL[id] + C + QL[mx] - QL[a])
                    break;
                else if (QL[id] - QL[mn] > QL[b] - QL[id] + C + QL[mn] - QL[a])
                {
                    mx = mn;
                    break;
                }
                else
                {
                    Mx = max(Mx, MaxD[id][0] + MaxD[id][id]);
                    found = 1;
                    break;
                }
            }
            md = (mn + mx)/2;
            if (QL[id] - QL[md] > QL[b] - QL[id] + C + QL[md] - QL[a])
                mn = md;
            else
                mx = md;
        }
        if (!found)
        {
            // printf("mx %d\n", mx);
            Mx = max(Mx, MaxD[id][mx + 1] + MaxD[id][id]);
            Mx = max(Mx, QL[b] - QL[id] + C + MaxD[a][mx] + MaxD[id][id]);
            Mx = max(Mx, QL[b] - QL[id] + C + MaxD[a][0] + MaxD[id][id]);
            Mx = max(Mx, QL[b] - QL[id] + C + MaxD[a][a] + MaxD[id][id]);
        }

        mn = id;
        mx = b;
        found = 0;
        while (1)
        {
            if (mx - mn <= 1)
            {
                if (QL[mn] - QL[id] > QL[b] - QL[mn] + C + QL[id] - QL[a])
                    break;
                else if (QL[mx] - QL[id] > QL[b] - QL[mx] + C + QL[id] - QL[a])
                {
                    mn = mx;
                    break;
                }
                else
                {
                    Mx = max(Mx, MaxD[id][N - 1] + MaxD[id][id]);
                    found = 1;
                    break;
                }
            }
            md = (mn + mx)/2;
            if (QL[md] - QL[id] > QL[b] - QL[md] + C + QL[id] - QL[a])
                mx = md;
            else
                mn = md;
        }
        if (!found)
        {
            // printf("mn %d\n", mn);
            Mx = max(Mx, MaxD[id][mn - 1] + MaxD[id][id]);
            Mx = max(Mx, QL[id] - QL[a] + C + MaxD[b][mn] + MaxD[id][id]);
            Mx = max(Mx, QL[id] - QL[a] + C + MaxD[b][b] + MaxD[id][id]);
            Mx = max(Mx, QL[id] - QL[a] + C + MaxD[b][N - 1] + MaxD[id][id]);
        }
        return Mx;
    }
    else if (id < a)
    {
        mn = a;
        mx = b;
        while (1)
        {
            if (mx - mn <= 1)
            {
                if (QL[mn] - QL[a] > C + QL[b] - QL[mn])
                    break;
                else if (QL[mx] - QL[a] > C + QL[b] - QL[mx])
                {
                    mn = mx;
                    break;
                }
                else
                    return INF;
            }
            md = (mn + mx)/2;
            if (QL[md] - QL[a] > C + QL[b] - QL[md])
                mx = md;
            else
                mn = md;
        }
        // printf("#mn %d\n", mn);
        Mx = MaxD[id][id] + MaxD[id][0];
        Mx = max(Mx, MaxD[id][mn - 1] + MaxD[id][id]);
        Mx = max(Mx, MaxD[id][id] + QL[a] - QL[id] + C + MaxD[b][N - 1]);
        Mx = max(Mx, MaxD[id][id] + QL[a] - QL[id] + C + MaxD[b][b]);
        Mx = max(Mx, MaxD[id][id] + QL[a] - QL[id] + C + MaxD[b][mn]);
        return Mx;
    }
    else
    {
        mn = a;
        mx = b;
        while (1)
        {
            if (mx - mn <= 1)
            {
                if (QL[b] - QL[mx] > C + QL[mx] - QL[a])
                    break;
                else if (QL[mn] - QL[a] > C + QL[b] - QL[mn])
                {
                    mx = mn;
                    break;
                }
                else
                    return INF;
            }
            md = (mn + mx)/2;
            if (QL[b] - QL[md] > C + QL[md] - QL[a])
                mn = md;
            else
                mx = md;
        }
        // printf("#mx %d\n", mx);
        Mx = MaxD[id][id] + MaxD[id][N - 1];
        Mx = max(Mx, MaxD[id][mx + 1] + MaxD[id][id]);
        Mx = max(Mx, MaxD[id][id] + QL[id] - QL[b] + C + MaxD[a][0]);
        Mx = max(Mx, MaxD[id][id] + QL[id] - QL[b] + C + MaxD[a][a]);
        Mx = max(Mx, MaxD[id][id] + QL[id] - QL[b] + C + MaxD[a][mx]);
        return Mx;
    }
}
long long find_shortcut(int n, std::vector<int> l, std::vector<int> d, int c)
{
    int i, j;
    N = n;
    C = c;
    long long sum;
    long long ans = 0;
    for (i = 1; i < n; i++)
        QL[i] = l[i - 1] + QL[i - 1];
    for (i = 0; i < n; i++)
    {
        sum = 0;
        MaxD[i][i] = 0;
        MD[i][i] = i;
        for (j = i - 1; j >= 0; j--)
        {
            sum += l[j];
            MaxD[i][j] = max(MaxD[i][j + 1], sum + d[j]);
            MD[i][j] = (MaxD[i][j] == sum + d[j])?j:MD[i][j + 1];
        }
        sum = 0;
        for (j = i + 1; j < n; j++)
        {
            sum += l[j - 1];
            MaxD[i][j] = max(MaxD[i][j - 1], sum + d[j]);
            MD[i][j] = (MaxD[i][j] == sum + d[j])?j:MD[i][j - 1];
        }
        MaxD[i][i] = d[i];
        ans = max(ans, max(d[i], MaxD[i][0]) + MaxD[i][n - 1]);
        ans = max(ans, max(d[i], MaxD[i][n - 1]) + MaxD[i][0]);
    }
    long long r;
    for (i = 0; i < n; i++)
    {
        for (j = i + 1; j < n; j++)
        {
            r = calc(i, j);
            // printf("i%d j%d r%lld\n", i, j, r);
            ans = min(ans, r);
        }
    }
    return ans;
}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB n = 4, 80 is a correct answer
2 Incorrect 2 ms 376 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 2 ms 376 KB n = 4, 80 is a correct answer
2 Incorrect 2 ms 376 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 2 ms 376 KB n = 4, 80 is a correct answer
2 Incorrect 2 ms 376 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 2 ms 376 KB n = 4, 80 is a correct answer
2 Incorrect 2 ms 376 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 2 ms 376 KB n = 4, 80 is a correct answer
2 Incorrect 2 ms 376 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 2 ms 376 KB n = 4, 80 is a correct answer
2 Incorrect 2 ms 376 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 2 ms 376 KB n = 4, 80 is a correct answer
2 Incorrect 2 ms 376 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 2 ms 376 KB n = 4, 80 is a correct answer
2 Incorrect 2 ms 376 KB n = 9, incorrect answer: jury 110 vs contestant 100
3 Halted 0 ms 0 KB -