oj.uz

Submission #71927

# Submission time Handle Problem Language Result Execution time Memory
71927 2018-08-25T21:25:44 Z XmtosX Shortcut (IOI16_shortcut) C++17
0 / 100
 3 ms 720 KB 
#include <bits/stdc++.h>
#include "shortcut.h"
using namespace std;
const int N=502;
long long dis[N][N],mx[N][N],mx1[N][N];
long long find_shortcut(int n, vector<int> l, vector<int> d, int c)
{
    if (n>500)
        return 0;
    for (int i=0;i<n;i++)
    {
            mx[i][i]=d[i];
            mx1[i][i]=d[i];
    }
    for (int i=0;i<n;i++)
    {
        for (int j=i+1;j<n;j++)
        {
            dis[i][j]=dis[i][j-1]+l[j-1];
            mx[i][j]=max(mx[i][j-1],dis[i][j]+d[j]);
        }
    }
    for (int i=0;i<n;i++)
    {
        for (int j=i-1;j>=0;j--)
        {
            mx1[j][i]=max(mx1[j+1][i],dis[j][i]+d[j]);
        }
    }
    long long ans=1e18;
    for (int i=0;i<n;i++)
    {
        for (int j=i+1;j<n;j++)
        {
            long long maxx=0;
            for (int q=0;q<n;q++)
            {
                long long cur=0;
                if (q==j&&j==n)
                {
                    cur= mx[j][n-1];
                }
                else if (q<=j)
                    cur= d[q]+mx[j][n-1]+(min(dis[q][j],dis[i][q]+c));
                if (q==0&&i==0)
                    cur= max(cur,mx1[0][i]);
                else if (q>=i)
                    cur= max(cur,d[q]+mx1[0][i]+min(dis[i][q],dis[q][j]+c));
                if (q>=i&&q<=j&&dis[q][j]+c<dis[i][q])
                {
                    int low=i,high=q-1,mid;
                    long long x=dis[q][j]+c;
                    while (low<=high)
                    {
                        mid= (low+high)/2;
                        if (x+dis[i][mid]<dis[mid][q])
                        {
                            cur=max(cur,x+d[q]+mx[i][mid]);
                            low=mid+1;
                        }
                        else
                        {
                            high=mid-1;
                            cur=max(cur,dis[mid][q]+d[q]+d[mid]);
                        }
                    }
                }
                maxx=max(maxx,cur);
            }
            ans=min(ans,maxx);
        }
    }
    return ans;
}

/*
int main()
{
    int n, c;
    assert(2 == scanf("%d%d", &n, &c));

    std::vector<int> l(n - 1);
    std::vector<int> d(n);
    for (int i = 0; i < n - 1; i++)
        assert(1 == scanf("%d", &l[i]));
    for (int i = 0; i < n; i++)
        assert(1 == scanf("%d", &d[i]));

    long long t = find_shortcut(n, l, d, c);


    printf("%lld\n", t);

    return 0;
}


*/

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB n = 4, 80 is a correct answer
2 Correct 2 ms 484 KB n = 9, 110 is a correct answer
3 Correct 2 ms 484 KB n = 4, 21 is a correct answer
4 Correct 3 ms 484 KB n = 3, 4 is a correct answer
5 Correct 2 ms 484 KB n = 2, 62 is a correct answer
6 Correct 2 ms 568 KB n = 2, 3 is a correct answer
7 Correct 3 ms 568 KB n = 3, 29 is a correct answer
8 Correct 2 ms 568 KB n = 2, 3 is a correct answer
9 Correct 2 ms 568 KB n = 2, 3 is a correct answer
10 Correct 2 ms 648 KB n = 2, 2000000001 is a correct answer
11 Correct 2 ms 664 KB n = 2, 3000000000 is a correct answer
12 Correct 2 ms 664 KB n = 3, 3000000000 is a correct answer
13 Correct 3 ms 664 KB n = 3, 3000000000 is a correct answer
14 Correct 2 ms 676 KB n = 4, 3000000001 is a correct answer
15 Correct 2 ms 676 KB n = 4, 4000000000 is a correct answer
16 Correct 2 ms 676 KB n = 5, 4000000000 is a correct answer
17 Incorrect 2 ms 720 KB n = 10, incorrect answer: jury 1000000343 vs contestant 1000000354
18 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB n = 4, 80 is a correct answer
2 Correct 2 ms 484 KB n = 9, 110 is a correct answer
3 Correct 2 ms 484 KB n = 4, 21 is a correct answer
4 Correct 3 ms 484 KB n = 3, 4 is a correct answer
5 Correct 2 ms 484 KB n = 2, 62 is a correct answer
6 Correct 2 ms 568 KB n = 2, 3 is a correct answer
7 Correct 3 ms 568 KB n = 3, 29 is a correct answer
8 Correct 2 ms 568 KB n = 2, 3 is a correct answer
9 Correct 2 ms 568 KB n = 2, 3 is a correct answer
10 Correct 2 ms 648 KB n = 2, 2000000001 is a correct answer
11 Correct 2 ms 664 KB n = 2, 3000000000 is a correct answer
12 Correct 2 ms 664 KB n = 3, 3000000000 is a correct answer
13 Correct 3 ms 664 KB n = 3, 3000000000 is a correct answer
14 Correct 2 ms 676 KB n = 4, 3000000001 is a correct answer
15 Correct 2 ms 676 KB n = 4, 4000000000 is a correct answer
16 Correct 2 ms 676 KB n = 5, 4000000000 is a correct answer
17 Incorrect 2 ms 720 KB n = 10, incorrect answer: jury 1000000343 vs contestant 1000000354
18 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB n = 4, 80 is a correct answer
2 Correct 2 ms 484 KB n = 9, 110 is a correct answer
3 Correct 2 ms 484 KB n = 4, 21 is a correct answer
4 Correct 3 ms 484 KB n = 3, 4 is a correct answer
5 Correct 2 ms 484 KB n = 2, 62 is a correct answer
6 Correct 2 ms 568 KB n = 2, 3 is a correct answer
7 Correct 3 ms 568 KB n = 3, 29 is a correct answer
8 Correct 2 ms 568 KB n = 2, 3 is a correct answer
9 Correct 2 ms 568 KB n = 2, 3 is a correct answer
10 Correct 2 ms 648 KB n = 2, 2000000001 is a correct answer
11 Correct 2 ms 664 KB n = 2, 3000000000 is a correct answer
12 Correct 2 ms 664 KB n = 3, 3000000000 is a correct answer
13 Correct 3 ms 664 KB n = 3, 3000000000 is a correct answer
14 Correct 2 ms 676 KB n = 4, 3000000001 is a correct answer
15 Correct 2 ms 676 KB n = 4, 4000000000 is a correct answer
16 Correct 2 ms 676 KB n = 5, 4000000000 is a correct answer
17 Incorrect 2 ms 720 KB n = 10, incorrect answer: jury 1000000343 vs contestant 1000000354
18 Halted 0 ms 0 KB -

Subtask #4
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB n = 4, 80 is a correct answer
2 Correct 2 ms 484 KB n = 9, 110 is a correct answer
3 Correct 2 ms 484 KB n = 4, 21 is a correct answer
4 Correct 3 ms 484 KB n = 3, 4 is a correct answer
5 Correct 2 ms 484 KB n = 2, 62 is a correct answer
6 Correct 2 ms 568 KB n = 2, 3 is a correct answer
7 Correct 3 ms 568 KB n = 3, 29 is a correct answer
8 Correct 2 ms 568 KB n = 2, 3 is a correct answer
9 Correct 2 ms 568 KB n = 2, 3 is a correct answer
10 Correct 2 ms 648 KB n = 2, 2000000001 is a correct answer
11 Correct 2 ms 664 KB n = 2, 3000000000 is a correct answer
12 Correct 2 ms 664 KB n = 3, 3000000000 is a correct answer
13 Correct 3 ms 664 KB n = 3, 3000000000 is a correct answer
14 Correct 2 ms 676 KB n = 4, 3000000001 is a correct answer
15 Correct 2 ms 676 KB n = 4, 4000000000 is a correct answer
16 Correct 2 ms 676 KB n = 5, 4000000000 is a correct answer
17 Incorrect 2 ms 720 KB n = 10, incorrect answer: jury 1000000343 vs contestant 1000000354
18 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB n = 4, 80 is a correct answer
2 Correct 2 ms 484 KB n = 9, 110 is a correct answer
3 Correct 2 ms 484 KB n = 4, 21 is a correct answer
4 Correct 3 ms 484 KB n = 3, 4 is a correct answer
5 Correct 2 ms 484 KB n = 2, 62 is a correct answer
6 Correct 2 ms 568 KB n = 2, 3 is a correct answer
7 Correct 3 ms 568 KB n = 3, 29 is a correct answer
8 Correct 2 ms 568 KB n = 2, 3 is a correct answer
9 Correct 2 ms 568 KB n = 2, 3 is a correct answer
10 Correct 2 ms 648 KB n = 2, 2000000001 is a correct answer
11 Correct 2 ms 664 KB n = 2, 3000000000 is a correct answer
12 Correct 2 ms 664 KB n = 3, 3000000000 is a correct answer
13 Correct 3 ms 664 KB n = 3, 3000000000 is a correct answer
14 Correct 2 ms 676 KB n = 4, 3000000001 is a correct answer
15 Correct 2 ms 676 KB n = 4, 4000000000 is a correct answer
16 Correct 2 ms 676 KB n = 5, 4000000000 is a correct answer
17 Incorrect 2 ms 720 KB n = 10, incorrect answer: jury 1000000343 vs contestant 1000000354
18 Halted 0 ms 0 KB -

Subtask #6
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB n = 4, 80 is a correct answer
2 Correct 2 ms 484 KB n = 9, 110 is a correct answer
3 Correct 2 ms 484 KB n = 4, 21 is a correct answer
4 Correct 3 ms 484 KB n = 3, 4 is a correct answer
5 Correct 2 ms 484 KB n = 2, 62 is a correct answer
6 Correct 2 ms 568 KB n = 2, 3 is a correct answer
7 Correct 3 ms 568 KB n = 3, 29 is a correct answer
8 Correct 2 ms 568 KB n = 2, 3 is a correct answer
9 Correct 2 ms 568 KB n = 2, 3 is a correct answer
10 Correct 2 ms 648 KB n = 2, 2000000001 is a correct answer
11 Correct 2 ms 664 KB n = 2, 3000000000 is a correct answer
12 Correct 2 ms 664 KB n = 3, 3000000000 is a correct answer
13 Correct 3 ms 664 KB n = 3, 3000000000 is a correct answer
14 Correct 2 ms 676 KB n = 4, 3000000001 is a correct answer
15 Correct 2 ms 676 KB n = 4, 4000000000 is a correct answer
16 Correct 2 ms 676 KB n = 5, 4000000000 is a correct answer
17 Incorrect 2 ms 720 KB n = 10, incorrect answer: jury 1000000343 vs contestant 1000000354
18 Halted 0 ms 0 KB -

Subtask #7
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB n = 4, 80 is a correct answer
2 Correct 2 ms 484 KB n = 9, 110 is a correct answer
3 Correct 2 ms 484 KB n = 4, 21 is a correct answer
4 Correct 3 ms 484 KB n = 3, 4 is a correct answer
5 Correct 2 ms 484 KB n = 2, 62 is a correct answer
6 Correct 2 ms 568 KB n = 2, 3 is a correct answer
7 Correct 3 ms 568 KB n = 3, 29 is a correct answer
8 Correct 2 ms 568 KB n = 2, 3 is a correct answer
9 Correct 2 ms 568 KB n = 2, 3 is a correct answer
10 Correct 2 ms 648 KB n = 2, 2000000001 is a correct answer
11 Correct 2 ms 664 KB n = 2, 3000000000 is a correct answer
12 Correct 2 ms 664 KB n = 3, 3000000000 is a correct answer
13 Correct 3 ms 664 KB n = 3, 3000000000 is a correct answer
14 Correct 2 ms 676 KB n = 4, 3000000001 is a correct answer
15 Correct 2 ms 676 KB n = 4, 4000000000 is a correct answer
16 Correct 2 ms 676 KB n = 5, 4000000000 is a correct answer
17 Incorrect 2 ms 720 KB n = 10, incorrect answer: jury 1000000343 vs contestant 1000000354
18 Halted 0 ms 0 KB -

Subtask #8
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB n = 4, 80 is a correct answer
2 Correct 2 ms 484 KB n = 9, 110 is a correct answer
3 Correct 2 ms 484 KB n = 4, 21 is a correct answer
4 Correct 3 ms 484 KB n = 3, 4 is a correct answer
5 Correct 2 ms 484 KB n = 2, 62 is a correct answer
6 Correct 2 ms 568 KB n = 2, 3 is a correct answer
7 Correct 3 ms 568 KB n = 3, 29 is a correct answer
8 Correct 2 ms 568 KB n = 2, 3 is a correct answer
9 Correct 2 ms 568 KB n = 2, 3 is a correct answer
10 Correct 2 ms 648 KB n = 2, 2000000001 is a correct answer
11 Correct 2 ms 664 KB n = 2, 3000000000 is a correct answer
12 Correct 2 ms 664 KB n = 3, 3000000000 is a correct answer
13 Correct 3 ms 664 KB n = 3, 3000000000 is a correct answer
14 Correct 2 ms 676 KB n = 4, 3000000001 is a correct answer
15 Correct 2 ms 676 KB n = 4, 4000000000 is a correct answer
16 Correct 2 ms 676 KB n = 5, 4000000000 is a correct answer
17 Incorrect 2 ms 720 KB n = 10, incorrect answer: jury 1000000343 vs contestant 1000000354
18 Halted 0 ms 0 KB -