oj.uz

Submission #276771

# Submission time Handle Problem Language Result Execution time Memory
276771 2020-08-20T16:31:12 Z arayi Shortcut (IOI16_shortcut) C++17
0 / 100
 1 ms 512 KB 
#include "shortcut.h"
#include <bits/stdc++.h>
#define lli long long int
using namespace std;

const int N = 500 + 30;

lli pr[N], aj[N][N], dz[N][N], pat, ret, a[N][N];
lli ds(int l, int r)
{
    if(l > r) swap(l, r);
    return pr[r] - pr[l];
}
long long find_shortcut(int n, vector<int> l, vector<int> d, int c)
{
    for (int i = 1; i < n; i++)
        pr[i] = pr[i-1] + l[i-1];
    for (int i = 0; i < n; i++)
    {
        a[i][i] = d[i];
        aj[i][i] = d[i];
        for (int j = i + 1; j < n; j++)
            aj[i][j] = max(aj[i][j-1], ds(i, j) + d[j]), pat = max(pat, d[i] + d[j] + ds(i, j));
        dz[i][i] = d[i];
        for(int j = i - 1; j >= 0; j--)
            dz[i][j] = max(dz[i][j + 1], ds(i, j) + d[j]), pat = max(pat, d[i] + d[j] + ds(i, j));
    }
    for (int i = 1; i < n; i++)
        for(int j = 0; j < n - i; j++)
            a[j][j + i] = max(max(a[j][j + i - 1], a[j + 1][j + i]), d[j] + d[j + i] + ds(j, j + i));
    ret = pat;
    for (int i = 0; i < n; i++)
    {
        for(int j = i + 1; j < n; j++)
        {
            if(c >= ds(i, j)) continue;
            lli sm = c + dz[i][0] + aj[j][n - 1];
            sm = max(sm, max(a[j][n-1], a[0][i]));
            int r = j;
            for(int k = i + 1; k < j; ++k)
            {
                sm = max(sm, d[k] + min(c + ds(k, i), ds(k, j)) + aj[j][n - 1]);
                sm = max(sm, d[k] + min(c + ds(j, k), ds(k, i)) + dz[i][0]);
                if(ds(k, i) + c < ds(k, j))
                {
                    while(ds(k, i) + c + ds(r - 1, j) < ds(k, r - 1)) r--;
                    sm = max(sm, aj[i][k] + c + dz[j][r]);
                }
                sm = max(sm, a[k][r - 1]);
            }
            ret = min(ret, sm);
        }
    }
    return ret;
}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB n = 4, 80 is a correct answer
2 Correct 1 ms 384 KB n = 9, 110 is a correct answer
3 Correct 0 ms 384 KB n = 4, 21 is a correct answer
4 Correct 1 ms 384 KB n = 3, 4 is a correct answer
5 Correct 0 ms 384 KB n = 2, 62 is a correct answer
6 Correct 0 ms 384 KB n = 2, 3 is a correct answer
7 Correct 0 ms 384 KB n = 3, 29 is a correct answer
8 Correct 0 ms 384 KB n = 2, 3 is a correct answer
9 Correct 0 ms 384 KB n = 2, 3 is a correct answer
10 Correct 1 ms 288 KB n = 2, 2000000001 is a correct answer
11 Correct 0 ms 384 KB n = 2, 3000000000 is a correct answer
12 Correct 1 ms 416 KB n = 3, 3000000000 is a correct answer
13 Correct 1 ms 384 KB n = 3, 3000000000 is a correct answer
14 Correct 0 ms 384 KB n = 4, 3000000001 is a correct answer
15 Correct 1 ms 384 KB n = 4, 4000000000 is a correct answer
16 Correct 0 ms 384 KB n = 5, 4000000000 is a correct answer
17 Correct 1 ms 384 KB n = 10, 1000000343 is a correct answer
18 Correct 1 ms 512 KB n = 10, 3189 is a correct answer
19 Correct 1 ms 512 KB n = 10, 7000000000 is a correct answer
20 Correct 1 ms 384 KB n = 5, 12 is a correct answer
21 Correct 1 ms 384 KB n = 5, 25 is a correct answer
22 Correct 1 ms 384 KB n = 2, 122 is a correct answer
23 Correct 1 ms 512 KB n = 10, 117 is a correct answer
24 Correct 1 ms 512 KB n = 10, 336 is a correct answer
25 Correct 1 ms 512 KB n = 10, 438 is a correct answer
26 Incorrect 1 ms 512 KB n = 10, incorrect answer: jury 206 vs contestant 217
27 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB n = 4, 80 is a correct answer
2 Correct 1 ms 384 KB n = 9, 110 is a correct answer
3 Correct 0 ms 384 KB n = 4, 21 is a correct answer
4 Correct 1 ms 384 KB n = 3, 4 is a correct answer
5 Correct 0 ms 384 KB n = 2, 62 is a correct answer
6 Correct 0 ms 384 KB n = 2, 3 is a correct answer
7 Correct 0 ms 384 KB n = 3, 29 is a correct answer
8 Correct 0 ms 384 KB n = 2, 3 is a correct answer
9 Correct 0 ms 384 KB n = 2, 3 is a correct answer
10 Correct 1 ms 288 KB n = 2, 2000000001 is a correct answer
11 Correct 0 ms 384 KB n = 2, 3000000000 is a correct answer
12 Correct 1 ms 416 KB n = 3, 3000000000 is a correct answer
13 Correct 1 ms 384 KB n = 3, 3000000000 is a correct answer
14 Correct 0 ms 384 KB n = 4, 3000000001 is a correct answer
15 Correct 1 ms 384 KB n = 4, 4000000000 is a correct answer
16 Correct 0 ms 384 KB n = 5, 4000000000 is a correct answer
17 Correct 1 ms 384 KB n = 10, 1000000343 is a correct answer
18 Correct 1 ms 512 KB n = 10, 3189 is a correct answer
19 Correct 1 ms 512 KB n = 10, 7000000000 is a correct answer
20 Correct 1 ms 384 KB n = 5, 12 is a correct answer
21 Correct 1 ms 384 KB n = 5, 25 is a correct answer
22 Correct 1 ms 384 KB n = 2, 122 is a correct answer
23 Correct 1 ms 512 KB n = 10, 117 is a correct answer
24 Correct 1 ms 512 KB n = 10, 336 is a correct answer
25 Correct 1 ms 512 KB n = 10, 438 is a correct answer
26 Incorrect 1 ms 512 KB n = 10, incorrect answer: jury 206 vs contestant 217
27 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB n = 4, 80 is a correct answer
2 Correct 1 ms 384 KB n = 9, 110 is a correct answer
3 Correct 0 ms 384 KB n = 4, 21 is a correct answer
4 Correct 1 ms 384 KB n = 3, 4 is a correct answer
5 Correct 0 ms 384 KB n = 2, 62 is a correct answer
6 Correct 0 ms 384 KB n = 2, 3 is a correct answer
7 Correct 0 ms 384 KB n = 3, 29 is a correct answer
8 Correct 0 ms 384 KB n = 2, 3 is a correct answer
9 Correct 0 ms 384 KB n = 2, 3 is a correct answer
10 Correct 1 ms 288 KB n = 2, 2000000001 is a correct answer
11 Correct 0 ms 384 KB n = 2, 3000000000 is a correct answer
12 Correct 1 ms 416 KB n = 3, 3000000000 is a correct answer
13 Correct 1 ms 384 KB n = 3, 3000000000 is a correct answer
14 Correct 0 ms 384 KB n = 4, 3000000001 is a correct answer
15 Correct 1 ms 384 KB n = 4, 4000000000 is a correct answer
16 Correct 0 ms 384 KB n = 5, 4000000000 is a correct answer
17 Correct 1 ms 384 KB n = 10, 1000000343 is a correct answer
18 Correct 1 ms 512 KB n = 10, 3189 is a correct answer
19 Correct 1 ms 512 KB n = 10, 7000000000 is a correct answer
20 Correct 1 ms 384 KB n = 5, 12 is a correct answer
21 Correct 1 ms 384 KB n = 5, 25 is a correct answer
22 Correct 1 ms 384 KB n = 2, 122 is a correct answer
23 Correct 1 ms 512 KB n = 10, 117 is a correct answer
24 Correct 1 ms 512 KB n = 10, 336 is a correct answer
25 Correct 1 ms 512 KB n = 10, 438 is a correct answer
26 Incorrect 1 ms 512 KB n = 10, incorrect answer: jury 206 vs contestant 217
27 Halted 0 ms 0 KB -

Subtask #4
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB n = 4, 80 is a correct answer
2 Correct 1 ms 384 KB n = 9, 110 is a correct answer
3 Correct 0 ms 384 KB n = 4, 21 is a correct answer
4 Correct 1 ms 384 KB n = 3, 4 is a correct answer
5 Correct 0 ms 384 KB n = 2, 62 is a correct answer
6 Correct 0 ms 384 KB n = 2, 3 is a correct answer
7 Correct 0 ms 384 KB n = 3, 29 is a correct answer
8 Correct 0 ms 384 KB n = 2, 3 is a correct answer
9 Correct 0 ms 384 KB n = 2, 3 is a correct answer
10 Correct 1 ms 288 KB n = 2, 2000000001 is a correct answer
11 Correct 0 ms 384 KB n = 2, 3000000000 is a correct answer
12 Correct 1 ms 416 KB n = 3, 3000000000 is a correct answer
13 Correct 1 ms 384 KB n = 3, 3000000000 is a correct answer
14 Correct 0 ms 384 KB n = 4, 3000000001 is a correct answer
15 Correct 1 ms 384 KB n = 4, 4000000000 is a correct answer
16 Correct 0 ms 384 KB n = 5, 4000000000 is a correct answer
17 Correct 1 ms 384 KB n = 10, 1000000343 is a correct answer
18 Correct 1 ms 512 KB n = 10, 3189 is a correct answer
19 Correct 1 ms 512 KB n = 10, 7000000000 is a correct answer
20 Correct 1 ms 384 KB n = 5, 12 is a correct answer
21 Correct 1 ms 384 KB n = 5, 25 is a correct answer
22 Correct 1 ms 384 KB n = 2, 122 is a correct answer
23 Correct 1 ms 512 KB n = 10, 117 is a correct answer
24 Correct 1 ms 512 KB n = 10, 336 is a correct answer
25 Correct 1 ms 512 KB n = 10, 438 is a correct answer
26 Incorrect 1 ms 512 KB n = 10, incorrect answer: jury 206 vs contestant 217
27 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB n = 4, 80 is a correct answer
2 Correct 1 ms 384 KB n = 9, 110 is a correct answer
3 Correct 0 ms 384 KB n = 4, 21 is a correct answer
4 Correct 1 ms 384 KB n = 3, 4 is a correct answer
5 Correct 0 ms 384 KB n = 2, 62 is a correct answer
6 Correct 0 ms 384 KB n = 2, 3 is a correct answer
7 Correct 0 ms 384 KB n = 3, 29 is a correct answer
8 Correct 0 ms 384 KB n = 2, 3 is a correct answer
9 Correct 0 ms 384 KB n = 2, 3 is a correct answer
10 Correct 1 ms 288 KB n = 2, 2000000001 is a correct answer
11 Correct 0 ms 384 KB n = 2, 3000000000 is a correct answer
12 Correct 1 ms 416 KB n = 3, 3000000000 is a correct answer
13 Correct 1 ms 384 KB n = 3, 3000000000 is a correct answer
14 Correct 0 ms 384 KB n = 4, 3000000001 is a correct answer
15 Correct 1 ms 384 KB n = 4, 4000000000 is a correct answer
16 Correct 0 ms 384 KB n = 5, 4000000000 is a correct answer
17 Correct 1 ms 384 KB n = 10, 1000000343 is a correct answer
18 Correct 1 ms 512 KB n = 10, 3189 is a correct answer
19 Correct 1 ms 512 KB n = 10, 7000000000 is a correct answer
20 Correct 1 ms 384 KB n = 5, 12 is a correct answer
21 Correct 1 ms 384 KB n = 5, 25 is a correct answer
22 Correct 1 ms 384 KB n = 2, 122 is a correct answer
23 Correct 1 ms 512 KB n = 10, 117 is a correct answer
24 Correct 1 ms 512 KB n = 10, 336 is a correct answer
25 Correct 1 ms 512 KB n = 10, 438 is a correct answer
26 Incorrect 1 ms 512 KB n = 10, incorrect answer: jury 206 vs contestant 217
27 Halted 0 ms 0 KB -

Subtask #6
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB n = 4, 80 is a correct answer
2 Correct 1 ms 384 KB n = 9, 110 is a correct answer
3 Correct 0 ms 384 KB n = 4, 21 is a correct answer
4 Correct 1 ms 384 KB n = 3, 4 is a correct answer
5 Correct 0 ms 384 KB n = 2, 62 is a correct answer
6 Correct 0 ms 384 KB n = 2, 3 is a correct answer
7 Correct 0 ms 384 KB n = 3, 29 is a correct answer
8 Correct 0 ms 384 KB n = 2, 3 is a correct answer
9 Correct 0 ms 384 KB n = 2, 3 is a correct answer
10 Correct 1 ms 288 KB n = 2, 2000000001 is a correct answer
11 Correct 0 ms 384 KB n = 2, 3000000000 is a correct answer
12 Correct 1 ms 416 KB n = 3, 3000000000 is a correct answer
13 Correct 1 ms 384 KB n = 3, 3000000000 is a correct answer
14 Correct 0 ms 384 KB n = 4, 3000000001 is a correct answer
15 Correct 1 ms 384 KB n = 4, 4000000000 is a correct answer
16 Correct 0 ms 384 KB n = 5, 4000000000 is a correct answer
17 Correct 1 ms 384 KB n = 10, 1000000343 is a correct answer
18 Correct 1 ms 512 KB n = 10, 3189 is a correct answer
19 Correct 1 ms 512 KB n = 10, 7000000000 is a correct answer
20 Correct 1 ms 384 KB n = 5, 12 is a correct answer
21 Correct 1 ms 384 KB n = 5, 25 is a correct answer
22 Correct 1 ms 384 KB n = 2, 122 is a correct answer
23 Correct 1 ms 512 KB n = 10, 117 is a correct answer
24 Correct 1 ms 512 KB n = 10, 336 is a correct answer
25 Correct 1 ms 512 KB n = 10, 438 is a correct answer
26 Incorrect 1 ms 512 KB n = 10, incorrect answer: jury 206 vs contestant 217
27 Halted 0 ms 0 KB -

Subtask #7
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB n = 4, 80 is a correct answer
2 Correct 1 ms 384 KB n = 9, 110 is a correct answer
3 Correct 0 ms 384 KB n = 4, 21 is a correct answer
4 Correct 1 ms 384 KB n = 3, 4 is a correct answer
5 Correct 0 ms 384 KB n = 2, 62 is a correct answer
6 Correct 0 ms 384 KB n = 2, 3 is a correct answer
7 Correct 0 ms 384 KB n = 3, 29 is a correct answer
8 Correct 0 ms 384 KB n = 2, 3 is a correct answer
9 Correct 0 ms 384 KB n = 2, 3 is a correct answer
10 Correct 1 ms 288 KB n = 2, 2000000001 is a correct answer
11 Correct 0 ms 384 KB n = 2, 3000000000 is a correct answer
12 Correct 1 ms 416 KB n = 3, 3000000000 is a correct answer
13 Correct 1 ms 384 KB n = 3, 3000000000 is a correct answer
14 Correct 0 ms 384 KB n = 4, 3000000001 is a correct answer
15 Correct 1 ms 384 KB n = 4, 4000000000 is a correct answer
16 Correct 0 ms 384 KB n = 5, 4000000000 is a correct answer
17 Correct 1 ms 384 KB n = 10, 1000000343 is a correct answer
18 Correct 1 ms 512 KB n = 10, 3189 is a correct answer
19 Correct 1 ms 512 KB n = 10, 7000000000 is a correct answer
20 Correct 1 ms 384 KB n = 5, 12 is a correct answer
21 Correct 1 ms 384 KB n = 5, 25 is a correct answer
22 Correct 1 ms 384 KB n = 2, 122 is a correct answer
23 Correct 1 ms 512 KB n = 10, 117 is a correct answer
24 Correct 1 ms 512 KB n = 10, 336 is a correct answer
25 Correct 1 ms 512 KB n = 10, 438 is a correct answer
26 Incorrect 1 ms 512 KB n = 10, incorrect answer: jury 206 vs contestant 217
27 Halted 0 ms 0 KB -

Subtask #8
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB n = 4, 80 is a correct answer
2 Correct 1 ms 384 KB n = 9, 110 is a correct answer
3 Correct 0 ms 384 KB n = 4, 21 is a correct answer
4 Correct 1 ms 384 KB n = 3, 4 is a correct answer
5 Correct 0 ms 384 KB n = 2, 62 is a correct answer
6 Correct 0 ms 384 KB n = 2, 3 is a correct answer
7 Correct 0 ms 384 KB n = 3, 29 is a correct answer
8 Correct 0 ms 384 KB n = 2, 3 is a correct answer
9 Correct 0 ms 384 KB n = 2, 3 is a correct answer
10 Correct 1 ms 288 KB n = 2, 2000000001 is a correct answer
11 Correct 0 ms 384 KB n = 2, 3000000000 is a correct answer
12 Correct 1 ms 416 KB n = 3, 3000000000 is a correct answer
13 Correct 1 ms 384 KB n = 3, 3000000000 is a correct answer
14 Correct 0 ms 384 KB n = 4, 3000000001 is a correct answer
15 Correct 1 ms 384 KB n = 4, 4000000000 is a correct answer
16 Correct 0 ms 384 KB n = 5, 4000000000 is a correct answer
17 Correct 1 ms 384 KB n = 10, 1000000343 is a correct answer
18 Correct 1 ms 512 KB n = 10, 3189 is a correct answer
19 Correct 1 ms 512 KB n = 10, 7000000000 is a correct answer
20 Correct 1 ms 384 KB n = 5, 12 is a correct answer
21 Correct 1 ms 384 KB n = 5, 25 is a correct answer
22 Correct 1 ms 384 KB n = 2, 122 is a correct answer
23 Correct 1 ms 512 KB n = 10, 117 is a correct answer
24 Correct 1 ms 512 KB n = 10, 336 is a correct answer
25 Correct 1 ms 512 KB n = 10, 438 is a correct answer
26 Incorrect 1 ms 512 KB n = 10, incorrect answer: jury 206 vs contestant 217
27 Halted 0 ms 0 KB -