oj.uz

Submission #889180

# Submission time Handle Problem Language Result Execution time Memory
889180 2023-12-19T06:39:25 Z Ghulam_Junaid Shortcut (IOI16_shortcut) C++17
0 / 100
 1 ms 2516 KB 
#include <bits/stdc++.h>
// #include "grader.cpp"
using namespace std;

typedef long long ll;

const int N = 3e3 + 10;
ll dist[N], initially[N][N], tmp[N][2], pmx[N], smx[N];

ll distance(ll u, ll v){
    if (u > v)
        swap(u, v);

    return dist[v] - dist[u];
} 

ll find_shortcut(int n, vector<int> l, vector<int> d, int c){
    dist[0] = 0;
    for (ll i=1; i<n; i++)
        dist[i] = dist[i - 1] + l[i - 1];

    for (ll u = 0; u < n; u++){
        for (ll v = 0; v < n; v++){
            if (u == v) continue;
            initially[u][v] = distance(u, v) + d[u] + d[v];
            pmx[max(u, v)] = max(pmx[max(u, v)], initially[u][v]);
            smx[min(u, v)] = max(smx[min(u, v)], initially[u][v]);
        }
    }

    for (int u = 1; u < n; u++)
        pmx[u] = max(pmx[u], pmx[u - 1]);
    for (int v = n - 2; v >= 0; v--)
        smx[v] = max(smx[v], smx[v + 1]);

    ll diam = 1e18;
    for (ll u = 0; u < n; u++){
        ll midmx = 0;
        for (ll v = u + 1; v < n; v++){
            // express line (u, v)

            // if (u != 7 or v != 8) continue;

            ll mx[4] = {0};
            ll ans = 0;
            for (ll x = 0; x < n; x++){
                if (x <= u){
                    tmp[x][0] = (ll)d[x] + distance(x, u);
                    mx[0] = max(mx[0], tmp[x][0]);
                }
                else if (u < x and x < v){
                    tmp[x][0] = (ll)d[x] + min(distance(x, u), distance(x, v) + c);
                    tmp[x][1] = (ll)d[x] + min(distance(x, v), distance(x, u) + c);
                    mx[1] = max(mx[1], tmp[x][0]);
                    mx[2] = max(mx[2], tmp[x][1]);
                }
                else if (v <= x){
                    tmp[x][1] = (ll)d[x] + distance(x, v);
                    mx[3] = max(mx[3], tmp[x][1]);
                }
            }

            for (ll x = u + 1; x < v - 1; x++){
                ll mind = distance(x, v - 1);
                mind = min(mind, distance(x, u) + c + distance(v - 1, v));
                midmx = max(midmx, mind + (ll)d[v - 1] + (ll)d[x]); 
            }

            ans = max(ans, pmx[u]);
            ans = max(ans, midmx);
            ans = max(ans, smx[v]);

            ans = max(ans, mx[0] + mx[3] + min((ll)c, distance(u, v)));
            ans = max(ans, mx[0] + mx[1]);
            ans = max(ans, mx[2] + mx[3]);
            // ans = max(ans, mx[3] + d[v]);
            // ans = max(ans, mx[2] + d[v]);
            // ans = max(ans, min(distance(u, v), c) + mx[0] + d[v]);

            // cout << u << " " << v << " " << mx[0] << " " << mx[1] << " " << mx[2] << " " << mx[3] << endl;

            diam = min(diam, ans);
            // if (ans == 100) cout << u << " ---- " << v << endl;
        }
    }

    return diam;
}

Subtask #1
0 / 9.0

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

Subtask #2
0 / 14.0

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

Subtask #3
0 / 8.0

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

Subtask #4
0 / 7.0

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

Subtask #5
0 / 33.0

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

Subtask #6
0 / 22.0

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

Subtask #7
0 / 4.0

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

Subtask #8
0 / 3.0

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