oj.uz

Submission #44850

# Submission time Handle Problem Language Result Execution time Memory
44850 2018-04-08T09:04:13 Z RayaBurong25_1 Shortcut (IOI16_shortcut) C++17
0 / 100
 2 ms 748 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 calc2(int a, int b, int id)
{
    //id = furthest from 0
    int found;
    int mn, md, mx;
    long long Mx;
    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
                {
                    if (id != 0) Mx = max(Mx, MaxD[id][0] + MaxD[id][id]);
                    else Mx = max(Mx, 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);
            if (mx + 1 != id) 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
                {
                    if (id != N - 1) Mx = max(Mx, MaxD[id][N - 1] + MaxD[id][id]);
                    else Mx = max(Mx, 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);
            if (mn - 1 != id) Mx = max(Mx, MaxD[id][mn - 1] + MaxD[id][id]);
            // printf("Mx %lld\n", Mx);
            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);
        if (id != 0) 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);
        if (id != N - 1) 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 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];
    std::vector<int> ID;
    long long idmx = 0;
    int id = 0;
    Mx = max(Mx, MaxD[0][mn - 1]);
    if (Mx == MaxD[0][mn - 1])
    {
        id = MD[0][mn - 1];
        if (Mx != idmx) ID.clear();
        ID.push_back(id);
        idmx = Mx;
    }
    Mx = max(Mx, QL[a] + C + MaxD[b][N - 1]);
    if (Mx == QL[a] + C + MaxD[b][N - 1])
    {
        id = MD[b][N - 1];
        if (Mx != idmx) ID.clear();
        ID.push_back(id);
        idmx = Mx;
    }
    Mx = max(Mx, QL[a] + C + MaxD[b][b]);
    if (Mx == QL[a] + C + MaxD[b][b])
    {
        id = MD[b][b];
        if (Mx != idmx) ID.clear();
        ID.push_back(id);
        idmx = Mx;
    }
    Mx = max(Mx, QL[a] + C + MaxD[b][mn]);
    if (Mx == QL[a] + C + MaxD[b][mn])
    {
        id = MD[b][mn];
        if (Mx != idmx) ID.clear();
        ID.push_back(id);
        idmx = Mx;
    }
    // printf("id%d\n", id);
    int i;
    Mx = 0;
    for (i = 0; i < ID.size(); i++)
    {
        // printf("id %d\n", id);
        Mx = max(Mx, calc2(a, b, ID[i]));
    }
    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;
}

Compilation message

shortcut.cpp: In function 'long long int calc(int, int)':
shortcut.cpp:230:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i = 0; i < ID.size(); i++)
                 ~~^~~~~~~~~~~
shortcut.cpp: In function 'long long int calc2(int, int, int)':
shortcut.cpp:22:15: warning: 'Mx' may be used uninitialized in this function [-Wmaybe-uninitialized]
     long long Mx;
               ^~

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 Correct 2 ms 572 KB n = 9, 110 is a correct answer
3 Correct 2 ms 572 KB n = 4, 21 is a correct answer
4 Correct 2 ms 620 KB n = 3, 4 is a correct answer
5 Correct 2 ms 620 KB n = 2, 62 is a correct answer
6 Correct 2 ms 620 KB n = 2, 3 is a correct answer
7 Correct 2 ms 620 KB n = 3, 29 is a correct answer
8 Correct 2 ms 620 KB n = 2, 3 is a correct answer
9 Correct 2 ms 620 KB n = 2, 3 is a correct answer
10 Correct 2 ms 620 KB n = 2, 2000000001 is a correct answer
11 Correct 2 ms 620 KB n = 2, 3000000000 is a correct answer
12 Correct 2 ms 620 KB n = 3, 3000000000 is a correct answer
13 Correct 2 ms 620 KB n = 3, 3000000000 is a correct answer
14 Correct 2 ms 620 KB n = 4, 3000000001 is a correct answer
15 Correct 2 ms 620 KB n = 4, 4000000000 is a correct answer
16 Correct 2 ms 620 KB n = 5, 4000000000 is a correct answer
17 Correct 2 ms 620 KB n = 10, 1000000343 is a correct answer
18 Correct 2 ms 748 KB n = 10, 3189 is a correct answer
19 Correct 2 ms 748 KB n = 10, 7000000000 is a correct answer
20 Incorrect 2 ms 748 KB n = 5, incorrect answer: jury 12 vs contestant 11
21 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 Correct 2 ms 572 KB n = 9, 110 is a correct answer
3 Correct 2 ms 572 KB n = 4, 21 is a correct answer
4 Correct 2 ms 620 KB n = 3, 4 is a correct answer
5 Correct 2 ms 620 KB n = 2, 62 is a correct answer
6 Correct 2 ms 620 KB n = 2, 3 is a correct answer
7 Correct 2 ms 620 KB n = 3, 29 is a correct answer
8 Correct 2 ms 620 KB n = 2, 3 is a correct answer
9 Correct 2 ms 620 KB n = 2, 3 is a correct answer
10 Correct 2 ms 620 KB n = 2, 2000000001 is a correct answer
11 Correct 2 ms 620 KB n = 2, 3000000000 is a correct answer
12 Correct 2 ms 620 KB n = 3, 3000000000 is a correct answer
13 Correct 2 ms 620 KB n = 3, 3000000000 is a correct answer
14 Correct 2 ms 620 KB n = 4, 3000000001 is a correct answer
15 Correct 2 ms 620 KB n = 4, 4000000000 is a correct answer
16 Correct 2 ms 620 KB n = 5, 4000000000 is a correct answer
17 Correct 2 ms 620 KB n = 10, 1000000343 is a correct answer
18 Correct 2 ms 748 KB n = 10, 3189 is a correct answer
19 Correct 2 ms 748 KB n = 10, 7000000000 is a correct answer
20 Incorrect 2 ms 748 KB n = 5, incorrect answer: jury 12 vs contestant 11
21 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 Correct 2 ms 572 KB n = 9, 110 is a correct answer
3 Correct 2 ms 572 KB n = 4, 21 is a correct answer
4 Correct 2 ms 620 KB n = 3, 4 is a correct answer
5 Correct 2 ms 620 KB n = 2, 62 is a correct answer
6 Correct 2 ms 620 KB n = 2, 3 is a correct answer
7 Correct 2 ms 620 KB n = 3, 29 is a correct answer
8 Correct 2 ms 620 KB n = 2, 3 is a correct answer
9 Correct 2 ms 620 KB n = 2, 3 is a correct answer
10 Correct 2 ms 620 KB n = 2, 2000000001 is a correct answer
11 Correct 2 ms 620 KB n = 2, 3000000000 is a correct answer
12 Correct 2 ms 620 KB n = 3, 3000000000 is a correct answer
13 Correct 2 ms 620 KB n = 3, 3000000000 is a correct answer
14 Correct 2 ms 620 KB n = 4, 3000000001 is a correct answer
15 Correct 2 ms 620 KB n = 4, 4000000000 is a correct answer
16 Correct 2 ms 620 KB n = 5, 4000000000 is a correct answer
17 Correct 2 ms 620 KB n = 10, 1000000343 is a correct answer
18 Correct 2 ms 748 KB n = 10, 3189 is a correct answer
19 Correct 2 ms 748 KB n = 10, 7000000000 is a correct answer
20 Incorrect 2 ms 748 KB n = 5, incorrect answer: jury 12 vs contestant 11
21 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 Correct 2 ms 572 KB n = 9, 110 is a correct answer
3 Correct 2 ms 572 KB n = 4, 21 is a correct answer
4 Correct 2 ms 620 KB n = 3, 4 is a correct answer
5 Correct 2 ms 620 KB n = 2, 62 is a correct answer
6 Correct 2 ms 620 KB n = 2, 3 is a correct answer
7 Correct 2 ms 620 KB n = 3, 29 is a correct answer
8 Correct 2 ms 620 KB n = 2, 3 is a correct answer
9 Correct 2 ms 620 KB n = 2, 3 is a correct answer
10 Correct 2 ms 620 KB n = 2, 2000000001 is a correct answer
11 Correct 2 ms 620 KB n = 2, 3000000000 is a correct answer
12 Correct 2 ms 620 KB n = 3, 3000000000 is a correct answer
13 Correct 2 ms 620 KB n = 3, 3000000000 is a correct answer
14 Correct 2 ms 620 KB n = 4, 3000000001 is a correct answer
15 Correct 2 ms 620 KB n = 4, 4000000000 is a correct answer
16 Correct 2 ms 620 KB n = 5, 4000000000 is a correct answer
17 Correct 2 ms 620 KB n = 10, 1000000343 is a correct answer
18 Correct 2 ms 748 KB n = 10, 3189 is a correct answer
19 Correct 2 ms 748 KB n = 10, 7000000000 is a correct answer
20 Incorrect 2 ms 748 KB n = 5, incorrect answer: jury 12 vs contestant 11
21 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 Correct 2 ms 572 KB n = 9, 110 is a correct answer
3 Correct 2 ms 572 KB n = 4, 21 is a correct answer
4 Correct 2 ms 620 KB n = 3, 4 is a correct answer
5 Correct 2 ms 620 KB n = 2, 62 is a correct answer
6 Correct 2 ms 620 KB n = 2, 3 is a correct answer
7 Correct 2 ms 620 KB n = 3, 29 is a correct answer
8 Correct 2 ms 620 KB n = 2, 3 is a correct answer
9 Correct 2 ms 620 KB n = 2, 3 is a correct answer
10 Correct 2 ms 620 KB n = 2, 2000000001 is a correct answer
11 Correct 2 ms 620 KB n = 2, 3000000000 is a correct answer
12 Correct 2 ms 620 KB n = 3, 3000000000 is a correct answer
13 Correct 2 ms 620 KB n = 3, 3000000000 is a correct answer
14 Correct 2 ms 620 KB n = 4, 3000000001 is a correct answer
15 Correct 2 ms 620 KB n = 4, 4000000000 is a correct answer
16 Correct 2 ms 620 KB n = 5, 4000000000 is a correct answer
17 Correct 2 ms 620 KB n = 10, 1000000343 is a correct answer
18 Correct 2 ms 748 KB n = 10, 3189 is a correct answer
19 Correct 2 ms 748 KB n = 10, 7000000000 is a correct answer
20 Incorrect 2 ms 748 KB n = 5, incorrect answer: jury 12 vs contestant 11
21 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 Correct 2 ms 572 KB n = 9, 110 is a correct answer
3 Correct 2 ms 572 KB n = 4, 21 is a correct answer
4 Correct 2 ms 620 KB n = 3, 4 is a correct answer
5 Correct 2 ms 620 KB n = 2, 62 is a correct answer
6 Correct 2 ms 620 KB n = 2, 3 is a correct answer
7 Correct 2 ms 620 KB n = 3, 29 is a correct answer
8 Correct 2 ms 620 KB n = 2, 3 is a correct answer
9 Correct 2 ms 620 KB n = 2, 3 is a correct answer
10 Correct 2 ms 620 KB n = 2, 2000000001 is a correct answer
11 Correct 2 ms 620 KB n = 2, 3000000000 is a correct answer
12 Correct 2 ms 620 KB n = 3, 3000000000 is a correct answer
13 Correct 2 ms 620 KB n = 3, 3000000000 is a correct answer
14 Correct 2 ms 620 KB n = 4, 3000000001 is a correct answer
15 Correct 2 ms 620 KB n = 4, 4000000000 is a correct answer
16 Correct 2 ms 620 KB n = 5, 4000000000 is a correct answer
17 Correct 2 ms 620 KB n = 10, 1000000343 is a correct answer
18 Correct 2 ms 748 KB n = 10, 3189 is a correct answer
19 Correct 2 ms 748 KB n = 10, 7000000000 is a correct answer
20 Incorrect 2 ms 748 KB n = 5, incorrect answer: jury 12 vs contestant 11
21 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 Correct 2 ms 572 KB n = 9, 110 is a correct answer
3 Correct 2 ms 572 KB n = 4, 21 is a correct answer
4 Correct 2 ms 620 KB n = 3, 4 is a correct answer
5 Correct 2 ms 620 KB n = 2, 62 is a correct answer
6 Correct 2 ms 620 KB n = 2, 3 is a correct answer
7 Correct 2 ms 620 KB n = 3, 29 is a correct answer
8 Correct 2 ms 620 KB n = 2, 3 is a correct answer
9 Correct 2 ms 620 KB n = 2, 3 is a correct answer
10 Correct 2 ms 620 KB n = 2, 2000000001 is a correct answer
11 Correct 2 ms 620 KB n = 2, 3000000000 is a correct answer
12 Correct 2 ms 620 KB n = 3, 3000000000 is a correct answer
13 Correct 2 ms 620 KB n = 3, 3000000000 is a correct answer
14 Correct 2 ms 620 KB n = 4, 3000000001 is a correct answer
15 Correct 2 ms 620 KB n = 4, 4000000000 is a correct answer
16 Correct 2 ms 620 KB n = 5, 4000000000 is a correct answer
17 Correct 2 ms 620 KB n = 10, 1000000343 is a correct answer
18 Correct 2 ms 748 KB n = 10, 3189 is a correct answer
19 Correct 2 ms 748 KB n = 10, 7000000000 is a correct answer
20 Incorrect 2 ms 748 KB n = 5, incorrect answer: jury 12 vs contestant 11
21 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 Correct 2 ms 572 KB n = 9, 110 is a correct answer
3 Correct 2 ms 572 KB n = 4, 21 is a correct answer
4 Correct 2 ms 620 KB n = 3, 4 is a correct answer
5 Correct 2 ms 620 KB n = 2, 62 is a correct answer
6 Correct 2 ms 620 KB n = 2, 3 is a correct answer
7 Correct 2 ms 620 KB n = 3, 29 is a correct answer
8 Correct 2 ms 620 KB n = 2, 3 is a correct answer
9 Correct 2 ms 620 KB n = 2, 3 is a correct answer
10 Correct 2 ms 620 KB n = 2, 2000000001 is a correct answer
11 Correct 2 ms 620 KB n = 2, 3000000000 is a correct answer
12 Correct 2 ms 620 KB n = 3, 3000000000 is a correct answer
13 Correct 2 ms 620 KB n = 3, 3000000000 is a correct answer
14 Correct 2 ms 620 KB n = 4, 3000000001 is a correct answer
15 Correct 2 ms 620 KB n = 4, 4000000000 is a correct answer
16 Correct 2 ms 620 KB n = 5, 4000000000 is a correct answer
17 Correct 2 ms 620 KB n = 10, 1000000343 is a correct answer
18 Correct 2 ms 748 KB n = 10, 3189 is a correct answer
19 Correct 2 ms 748 KB n = 10, 7000000000 is a correct answer
20 Incorrect 2 ms 748 KB n = 5, incorrect answer: jury 12 vs contestant 11
21 Halted 0 ms 0 KB -