답안 #44847 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
44847	2018-04-08T08:43:34 Z	RayaBurong25_1	Shortcut (IOI16_shortcut)	C++17	0 / 100	2 ms	552 KB

shortcut

#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
                {
                    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 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++)
        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:227:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i = 0; i < ID.size(); i++)
                 ~~^~~~~~~~~~~

Subtask #1
0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	n = 4, 80 is a correct answer
2	Correct	2 ms	396 KB	n = 9, 110 is a correct answer
3	Correct	2 ms	416 KB	n = 4, 21 is a correct answer
4	Correct	2 ms	472 KB	n = 3, 4 is a correct answer
5	Incorrect	2 ms	552 KB	n = 2, incorrect answer: jury 62 vs contestant 72
6	Halted	0 ms	0 KB	-

Subtask #2
0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	n = 4, 80 is a correct answer
2	Correct	2 ms	396 KB	n = 9, 110 is a correct answer
3	Correct	2 ms	416 KB	n = 4, 21 is a correct answer
4	Correct	2 ms	472 KB	n = 3, 4 is a correct answer
5	Incorrect	2 ms	552 KB	n = 2, incorrect answer: jury 62 vs contestant 72
6	Halted	0 ms	0 KB	-

Subtask #3
0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	n = 4, 80 is a correct answer
2	Correct	2 ms	396 KB	n = 9, 110 is a correct answer
3	Correct	2 ms	416 KB	n = 4, 21 is a correct answer
4	Correct	2 ms	472 KB	n = 3, 4 is a correct answer
5	Incorrect	2 ms	552 KB	n = 2, incorrect answer: jury 62 vs contestant 72
6	Halted	0 ms	0 KB	-

Subtask #4
0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	n = 4, 80 is a correct answer
2	Correct	2 ms	396 KB	n = 9, 110 is a correct answer
3	Correct	2 ms	416 KB	n = 4, 21 is a correct answer
4	Correct	2 ms	472 KB	n = 3, 4 is a correct answer
5	Incorrect	2 ms	552 KB	n = 2, incorrect answer: jury 62 vs contestant 72
6	Halted	0 ms	0 KB	-

Subtask #5
0 / 33.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	n = 4, 80 is a correct answer
2	Correct	2 ms	396 KB	n = 9, 110 is a correct answer
3	Correct	2 ms	416 KB	n = 4, 21 is a correct answer
4	Correct	2 ms	472 KB	n = 3, 4 is a correct answer
5	Incorrect	2 ms	552 KB	n = 2, incorrect answer: jury 62 vs contestant 72
6	Halted	0 ms	0 KB	-

Subtask #6
0 / 22.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	n = 4, 80 is a correct answer
2	Correct	2 ms	396 KB	n = 9, 110 is a correct answer
3	Correct	2 ms	416 KB	n = 4, 21 is a correct answer
4	Correct	2 ms	472 KB	n = 3, 4 is a correct answer
5	Incorrect	2 ms	552 KB	n = 2, incorrect answer: jury 62 vs contestant 72
6	Halted	0 ms	0 KB	-

Subtask #7
0 / 4.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	n = 4, 80 is a correct answer
2	Correct	2 ms	396 KB	n = 9, 110 is a correct answer
3	Correct	2 ms	416 KB	n = 4, 21 is a correct answer
4	Correct	2 ms	472 KB	n = 3, 4 is a correct answer
5	Incorrect	2 ms	552 KB	n = 2, incorrect answer: jury 62 vs contestant 72
6	Halted	0 ms	0 KB	-

Subtask #8
0 / 3.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	n = 4, 80 is a correct answer
2	Correct	2 ms	396 KB	n = 9, 110 is a correct answer
3	Correct	2 ms	416 KB	n = 4, 21 is a correct answer
4	Correct	2 ms	472 KB	n = 3, 4 is a correct answer
5	Incorrect	2 ms	552 KB	n = 2, incorrect answer: jury 62 vs contestant 72
6	Halted	0 ms	0 KB	-