oj.uz

Submission #1042719

# Submission time Handle Problem Language Result Execution time Memory
1042719 2024-08-03T10:06:11 Z Zicrus Shortcut (IOI16_shortcut) C++17
0 / 100
 1 ms 604 KB 
#include <bits/stdc++.h>
#include "shortcut.h"
using namespace std;

typedef long long ll;

ll find_shortcut(int n, vector<int> l, vector<int> s, int c) {
    vector<ll> dist(n);
    vector<pair<ll, ll>> preMax(n), postMax(n);
    preMax[0] = {s[0], 0};
    for (int i = 1; i < n; i++) {
        dist[i] = dist[i-1] + l[i-1];
        preMax[i] = {dist[i] + s[i], i};
        if (preMax[i-1].first > preMax[i].first) preMax[i] = preMax[i-1];
    }
    postMax[n-1] = {dist[n-1] + s[n-1], n-1};
    for (int i = n-2; i >= 0; i--) {
        postMax[i] = {dist[i] + s[i], i};
        if (postMax[i+1].first > postMax[i].first) postMax[i] = postMax[i+1];
    }

    ll res = 1ll << 62ll;
    for (int low = 0; low < n-1; low++) {
        for (int high = low+1; high < n; high++) {
            // First search
            ll mx = preMax[low].first, mxId = preMax[low].second;
            ll mxFromHigh = postMax[high].first - (dist[high] - dist[low]) + min(dist[high] - dist[low], (ll)c);
            if (mxFromHigh > mx) {
                mx = mxFromHigh;
                mxId = postMax[high].second;
            }
            for (int i = low+1; i < high; i++) {
                ll val = min(dist[i], dist[low] + c + (dist[high] - dist[i])) + s[i];
                if (val > mx) {
                    mx = val;
                    mxId = i;
                }
            }

            // Second search
            ll dst = 0;
            ll dia = 0;
            for (int i = mxId-1; i >= 0; i--) {
                dst += l[i];
                ll ths = min(dst, abs(dist[mxId] - dist[high]) + c + abs(dist[low] - dist[i])) + s[i];
                dia = max(dia, ths);
            }
            dst = 0;
            for (int i = mxId+1; i < n; i++) {
                dst += l[i-1];
                ll ths = min(dst, abs(dist[mxId] - dist[low]) + c + abs(dist[high] - dist[i])) + s[i];
                dia = max(dia, ths);
            }
            dia += s[mxId];
            res = min(res, dia);
        }
    }

    return res;
}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB n = 4, 80 is a correct answer
2 Correct 0 ms 348 KB n = 9, 110 is a correct answer
3 Correct 0 ms 604 KB n = 4, 21 is a correct answer
4 Correct 0 ms 436 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 344 KB n = 3, 29 is a correct answer
8 Correct 0 ms 344 KB n = 2, 3 is a correct answer
9 Correct 0 ms 604 KB n = 2, 3 is a correct answer
10 Correct 1 ms 348 KB n = 2, 2000000001 is a correct answer
11 Correct 0 ms 348 KB n = 2, 3000000000 is a correct answer
12 Correct 0 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 0 ms 348 KB n = 5, 4000000000 is a correct answer
17 Correct 0 ms 348 KB n = 10, 1000000343 is a correct answer
18 Correct 0 ms 348 KB n = 10, 3189 is a correct answer
19 Correct 0 ms 344 KB n = 10, 7000000000 is a correct answer
20 Incorrect 0 ms 344 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 0 ms 348 KB n = 4, 80 is a correct answer
2 Correct 0 ms 348 KB n = 9, 110 is a correct answer
3 Correct 0 ms 604 KB n = 4, 21 is a correct answer
4 Correct 0 ms 436 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 344 KB n = 3, 29 is a correct answer
8 Correct 0 ms 344 KB n = 2, 3 is a correct answer
9 Correct 0 ms 604 KB n = 2, 3 is a correct answer
10 Correct 1 ms 348 KB n = 2, 2000000001 is a correct answer
11 Correct 0 ms 348 KB n = 2, 3000000000 is a correct answer
12 Correct 0 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 0 ms 348 KB n = 5, 4000000000 is a correct answer
17 Correct 0 ms 348 KB n = 10, 1000000343 is a correct answer
18 Correct 0 ms 348 KB n = 10, 3189 is a correct answer
19 Correct 0 ms 344 KB n = 10, 7000000000 is a correct answer
20 Incorrect 0 ms 344 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 0 ms 348 KB n = 4, 80 is a correct answer
2 Correct 0 ms 348 KB n = 9, 110 is a correct answer
3 Correct 0 ms 604 KB n = 4, 21 is a correct answer
4 Correct 0 ms 436 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 344 KB n = 3, 29 is a correct answer
8 Correct 0 ms 344 KB n = 2, 3 is a correct answer
9 Correct 0 ms 604 KB n = 2, 3 is a correct answer
10 Correct 1 ms 348 KB n = 2, 2000000001 is a correct answer
11 Correct 0 ms 348 KB n = 2, 3000000000 is a correct answer
12 Correct 0 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 0 ms 348 KB n = 5, 4000000000 is a correct answer
17 Correct 0 ms 348 KB n = 10, 1000000343 is a correct answer
18 Correct 0 ms 348 KB n = 10, 3189 is a correct answer
19 Correct 0 ms 344 KB n = 10, 7000000000 is a correct answer
20 Incorrect 0 ms 344 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 0 ms 348 KB n = 4, 80 is a correct answer
2 Correct 0 ms 348 KB n = 9, 110 is a correct answer
3 Correct 0 ms 604 KB n = 4, 21 is a correct answer
4 Correct 0 ms 436 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 344 KB n = 3, 29 is a correct answer
8 Correct 0 ms 344 KB n = 2, 3 is a correct answer
9 Correct 0 ms 604 KB n = 2, 3 is a correct answer
10 Correct 1 ms 348 KB n = 2, 2000000001 is a correct answer
11 Correct 0 ms 348 KB n = 2, 3000000000 is a correct answer
12 Correct 0 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 0 ms 348 KB n = 5, 4000000000 is a correct answer
17 Correct 0 ms 348 KB n = 10, 1000000343 is a correct answer
18 Correct 0 ms 348 KB n = 10, 3189 is a correct answer
19 Correct 0 ms 344 KB n = 10, 7000000000 is a correct answer
20 Incorrect 0 ms 344 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 0 ms 348 KB n = 4, 80 is a correct answer
2 Correct 0 ms 348 KB n = 9, 110 is a correct answer
3 Correct 0 ms 604 KB n = 4, 21 is a correct answer
4 Correct 0 ms 436 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 344 KB n = 3, 29 is a correct answer
8 Correct 0 ms 344 KB n = 2, 3 is a correct answer
9 Correct 0 ms 604 KB n = 2, 3 is a correct answer
10 Correct 1 ms 348 KB n = 2, 2000000001 is a correct answer
11 Correct 0 ms 348 KB n = 2, 3000000000 is a correct answer
12 Correct 0 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 0 ms 348 KB n = 5, 4000000000 is a correct answer
17 Correct 0 ms 348 KB n = 10, 1000000343 is a correct answer
18 Correct 0 ms 348 KB n = 10, 3189 is a correct answer
19 Correct 0 ms 344 KB n = 10, 7000000000 is a correct answer
20 Incorrect 0 ms 344 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 0 ms 348 KB n = 4, 80 is a correct answer
2 Correct 0 ms 348 KB n = 9, 110 is a correct answer
3 Correct 0 ms 604 KB n = 4, 21 is a correct answer
4 Correct 0 ms 436 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 344 KB n = 3, 29 is a correct answer
8 Correct 0 ms 344 KB n = 2, 3 is a correct answer
9 Correct 0 ms 604 KB n = 2, 3 is a correct answer
10 Correct 1 ms 348 KB n = 2, 2000000001 is a correct answer
11 Correct 0 ms 348 KB n = 2, 3000000000 is a correct answer
12 Correct 0 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 0 ms 348 KB n = 5, 4000000000 is a correct answer
17 Correct 0 ms 348 KB n = 10, 1000000343 is a correct answer
18 Correct 0 ms 348 KB n = 10, 3189 is a correct answer
19 Correct 0 ms 344 KB n = 10, 7000000000 is a correct answer
20 Incorrect 0 ms 344 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 0 ms 348 KB n = 4, 80 is a correct answer
2 Correct 0 ms 348 KB n = 9, 110 is a correct answer
3 Correct 0 ms 604 KB n = 4, 21 is a correct answer
4 Correct 0 ms 436 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 344 KB n = 3, 29 is a correct answer
8 Correct 0 ms 344 KB n = 2, 3 is a correct answer
9 Correct 0 ms 604 KB n = 2, 3 is a correct answer
10 Correct 1 ms 348 KB n = 2, 2000000001 is a correct answer
11 Correct 0 ms 348 KB n = 2, 3000000000 is a correct answer
12 Correct 0 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 0 ms 348 KB n = 5, 4000000000 is a correct answer
17 Correct 0 ms 348 KB n = 10, 1000000343 is a correct answer
18 Correct 0 ms 348 KB n = 10, 3189 is a correct answer
19 Correct 0 ms 344 KB n = 10, 7000000000 is a correct answer
20 Incorrect 0 ms 344 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 0 ms 348 KB n = 4, 80 is a correct answer
2 Correct 0 ms 348 KB n = 9, 110 is a correct answer
3 Correct 0 ms 604 KB n = 4, 21 is a correct answer
4 Correct 0 ms 436 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 344 KB n = 3, 29 is a correct answer
8 Correct 0 ms 344 KB n = 2, 3 is a correct answer
9 Correct 0 ms 604 KB n = 2, 3 is a correct answer
10 Correct 1 ms 348 KB n = 2, 2000000001 is a correct answer
11 Correct 0 ms 348 KB n = 2, 3000000000 is a correct answer
12 Correct 0 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 0 ms 348 KB n = 5, 4000000000 is a correct answer
17 Correct 0 ms 348 KB n = 10, 1000000343 is a correct answer
18 Correct 0 ms 348 KB n = 10, 3189 is a correct answer
19 Correct 0 ms 344 KB n = 10, 7000000000 is a correct answer
20 Incorrect 0 ms 344 KB n = 5, incorrect answer: jury 12 vs contestant 11
21 Halted 0 ms 0 KB -