oj.uz

Submission #1042810

# Submission time Handle Problem Language Result Execution time Memory
1042810 2024-08-03T12:19:20 Z Zicrus Shortcut (IOI16_shortcut) C++17
0 / 100
 1 ms 348 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), preMax(n), postMax(n);
    preMax[0] = s[0];
    for (int i = 1; i < n; i++) {
        dist[i] = dist[i-1] + l[i-1];
        preMax[i] = max(preMax[i-1] + l[i-1], (ll)s[i]);
    }
    postMax[n-1] = s[n-1];
    for (int i = n-2; i >= 0; i--) {
        postMax[i] = max(postMax[i+1] + l[i], (ll)s[i]);
    }

    ll res = 1ll << 62ll;
    for (int low = 0; low < n-1; low++) {
        for (int high = low+1; high < n; high++) {
            if (c >= dist[high] - dist[low]) continue;

            // Left to right
            ll dia = c + preMax[low] + postMax[high];

            // Left to mid
            ll id = low+1; // First id where it's better to take the highway
            while (id < high) {
                if (dist[id] - dist[low] >= c + dist[high] - dist[id]) break;
                // Normal route
                dia = max(dia, preMax[low] + dist[id] - dist[low] + s[id]);
                id++;
            }
            for (int i = id; i < high; i++) {
                dia = max(dia, preMax[low] + c + dist[high] - dist[i] + s[i]);
            }

            // Right to mid
            id = high-1; // First id where it's better to take the highway
            while (id > low) {
                if (dist[high] - dist[id] >= c + dist[id] - dist[low]) break;
                // Normal route
                dia = max(dia, postMax[high] + dist[high] - dist[id] + s[id]);
                id--;
            }
            for (int i = id; i > low; i--) {
                dia = max(dia, postMax[high] + c + dist[i] - dist[low] + s[i]);
            }

            // Mid
            for (int i = low; i < high; i++) {
                for (int j = i+1; j <= high; j++) {
                    ll dst = min(dist[j] - dist[i], abs(dist[i] - dist[low]) + c + abs(dist[high] - dist[j])) + s[i] + s[j];
                    dia = max(dia, dst);
                }
            }

            res = min(res, dia);
        }
    }

    return res;
}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB n = 4, 80 is a correct answer
2 Correct 0 ms 348 KB n = 9, 110 is a correct answer
3 Incorrect 0 ms 348 KB n = 4, incorrect answer: jury 21 vs contestant 14
4 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB n = 4, 80 is a correct answer
2 Correct 0 ms 348 KB n = 9, 110 is a correct answer
3 Incorrect 0 ms 348 KB n = 4, incorrect answer: jury 21 vs contestant 14
4 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB n = 4, 80 is a correct answer
2 Correct 0 ms 348 KB n = 9, 110 is a correct answer
3 Incorrect 0 ms 348 KB n = 4, incorrect answer: jury 21 vs contestant 14
4 Halted 0 ms 0 KB -

Subtask #4
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB n = 4, 80 is a correct answer
2 Correct 0 ms 348 KB n = 9, 110 is a correct answer
3 Incorrect 0 ms 348 KB n = 4, incorrect answer: jury 21 vs contestant 14
4 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB n = 4, 80 is a correct answer
2 Correct 0 ms 348 KB n = 9, 110 is a correct answer
3 Incorrect 0 ms 348 KB n = 4, incorrect answer: jury 21 vs contestant 14
4 Halted 0 ms 0 KB -

Subtask #6
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB n = 4, 80 is a correct answer
2 Correct 0 ms 348 KB n = 9, 110 is a correct answer
3 Incorrect 0 ms 348 KB n = 4, incorrect answer: jury 21 vs contestant 14
4 Halted 0 ms 0 KB -

Subtask #7
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB n = 4, 80 is a correct answer
2 Correct 0 ms 348 KB n = 9, 110 is a correct answer
3 Incorrect 0 ms 348 KB n = 4, incorrect answer: jury 21 vs contestant 14
4 Halted 0 ms 0 KB -

Subtask #8
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB n = 4, 80 is a correct answer
2 Correct 0 ms 348 KB n = 9, 110 is a correct answer
3 Incorrect 0 ms 348 KB n = 4, incorrect answer: jury 21 vs contestant 14
4 Halted 0 ms 0 KB -