Submission #1267807

#	Time	Username	Problem	Language	Result	Execution time	Memory
1267807		silentloop	Shortcut (IOI16_shortcut)	C++20	0 / 100	0 ms	320 KiB

shortcut

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

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

    vector<ll> left_max(n, 0);
    for (int a = 0; a < n; a++) {
        ll max_left = 0;
        for (int i = 0; i < a; i++) {
            max_left = max(max_left, (ll)d[i] + (x[a] - x[i]));
        }
        left_max[a] = max_left;
    }

    vector<ll> right_max(n, 0);
    for (int b = 0; b < n; b++) {
        ll max_right = 0;
        for (int i = b + 1; i < n; i++) {
            max_right = max(max_right, (ll)d[i] + (x[i] - x[b])); 
        }
        right_max[b] = max_right;
    }

    ll ans = LLONG_MAX; 

    for (int a = 0; a < n; a++) {
        for (int b = a + 1; b < n; b++) {
            ll D = x[b] - x[a]; 
            ll S = D + c; 

            ll left_branch = (a > 0) ? left_max[a] : 0;
            ll right_branch = (b < n - 1) ? right_max[b] : 0;

            int m = b - a + 1; 
            vector<ll> p(m); 
            for (int k = 0; k < m; k++) {
                p[k] = x[a + k] - x[a]; 
            }

            vector<ll> temp(m, 0);
            for (int u = 0; u < m; u++) {
                ll max_dist = d[a + u]; 
                deque<int> dq; 

                for (int v = 0; v < m; v++) {
                    ll dist = min(abs(p[u] - p[v]), S - abs(p[u] - p[v]));
                    ll val = d[a + v] + dist;
                    while (!dq.empty() && val >= d[a + dq.back()] + dist) {
                        dq.pop_back();
                    }
                    dq.push_back(v);
                }
                temp[u] = d[a + u] + (dq.empty() ? 0 : d[a + dq.front()] + min(abs(p[u] - p[dq.front()]), S - abs(p[u] - p[dq.front()])));
            }

            ll cycle_diam = 0;
            for (int u = 0; u < m; u++) {
                cycle_diam = max(cycle_diam, temp[u]);
            }

            ll cross_left = 0, cross_right = 0;
            for (int u = 0; u < a; u++) {
                cross_left = max(cross_left, (ll)d[u] + min(x[a] - x[u], x[b] - x[u] + c));
            }
            for (int u = b + 1; u < n; u++) {
                cross_right = max(cross_right, (ll)d[u] + min(x[u] - x[b], x[u] - x[a] + c));
            }

            ll total_diam = max({left_branch, right_branch, cycle_diam, cross_left, cross_right});
            ans = min(ans, total_diam);
        }
    }

    return ans; 
}

Compilation message (stderr)

shortcut.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
shortcut_c.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~

• Subtask 1: 0 / 9
• Subtask 2: 0 / 14
• Subtask 3: 0 / 8
• Subtask 4: 0 / 7
• Subtask 5: 0 / 33
• Subtask 6: 0 / 22
• Subtask 7: 0 / 4
• Subtask 8: 0 / 3