Submission #889184

#	Time	Username	Problem	Language	Result	Execution time	Memory
889184		Ghulam_Junaid	Shortcut (IOI16_shortcut)	C++17	0 / 100	1 ms	2396 KiB

shortcut

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

typedef long long ll;

const ll N = 3005;
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){
    vector<ll> l, d;
    for (auto x:L) l.push_back(x);
    for (auto x:D) d.push_back(x);
    ll n = N;
    ll c = 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 (ll u = 1; u < n; u++)
        pmx[u] = max(pmx[u], pmx[u - 1]);
    for (ll 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[0] + d[u]);
            ans = max(ans, mx[1] + d[u]);
            ans = max(ans, d[u] + mx[3] + min((ll)c, distance(u, v)));

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

            ans = max(ans, d[u] + d[v] + min((ll)c, distance(u, v)));
            // 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
• 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