Submission #1069989

#	Time	Username	Problem	Language	Result	Execution time	Memory
1069989		mc061	Shortcut (IOI16_shortcut)	C++14	0 / 100	1 ms	8540 KiB

shortcut

#pragma once
#include <bits/stdc++.h>
using namespace std;
 
template<typename T>
using minheap = priority_queue<T, vector<T>, greater<T>>;
 
const int64_t INF = 1e18;
const int N = 3e3+6;
const int L = 13;
int64_t dist[N][N];
int64_t pref_maxA[N][N]={};
int64_t suf_maxB[N][N][13]={};
int64_t D[N];
int64_t fast_log[N];

int64_t furthest_pref[N];
int64_t furthest_suf[N];

void build_sparse(int n, int i) {
    for (int j = i+1; j < n; ++j) {
        suf_maxB[i][j][0] = D[j]+D[i]-dist[i][j];
    }
    for (int k = 1; k < L; ++k) {
        for (int j = i+1; j+(1<<k) <= n; ++j) {
            suf_maxB[i][j][k] = max(suf_maxB[i][j][k-1], suf_maxB[i][j+(1<<(k-1))][k-1]);
        }
    }
}
int64_t query_sparse(int i, int l, int r) {
    int k = fast_log[r-l+1];
    return max(suf_maxB[i][l][k], suf_maxB[i][r-(1<<k)+1][k]);
}
 
long long find_shortcut(int n, vector<int> l, vector<int> d, int c) {
    fast_log[1] = 0;
    for (int i = 2; i < N; ++i) {
        fast_log[i] = fast_log[i/2]+1;
    }
    for (int i = 0; i < n; ++i) {
        dist[i][i] = 0;
        for (int j = i+1; j < n; ++j) {
            dist[i][j] = dist[j][i] = dist[i][j-1]+l[j-1];
        }
    }

    for (int i = 0; i < n; ++i) {
        pref_maxA[i][i] = d[i];
        for (int j = i+1; j < n; ++j) {
            pref_maxA[i][j] = max(pref_maxA[i][j-1], dist[i][j]+d[i]+d[j]);
        }
    }
    for (int i = 0; i < n; ++i) {
        build_sparse(n, i);
    }
    furthest_pref[0] = d[0];
    for (int i = 1; i < n; ++i) {
        furthest_pref[i] = max<int64_t>(furthest_pref[i-1]+l[i-1], d[i]);
    }
    furthest_suf[n-1] = d[n-1];
    for (int i = n-2; i >= 0; --i) {
        furthest_suf[i] = max<int64_t>(furthest_suf[i+1]+l[i], d[i]);
    }

    int64_t res = 1e18;
    for (int i = 0; i < n; ++i) {
        int ptr[n]={};
        for (int j = i+1; j < n; ++j) ptr[j]=j;
        int64_t tot_w = c;
        for (int j = i+1; j < n; ++j) {
            tot_w += l[j-1];
            int64_t mx = 0;
            auto upd_pr = [&] (int idx) {
                if (!(idx >= i && idx <= j)) return;
                mx = max(mx, furthest_pref[i] + min(dist[i][idx], tot_w-dist[i][idx])+d[idx]);
            };
            auto upd_suf = [&] (int idx) {
                if (!(idx >= i && idx <= j)) return;
                mx = max(mx, furthest_suf[j] + min(tot_w-dist[j][idx], dist[j][idx])+d[idx]);
            };
            for (int k = i; k <= j; ++k) {
                while (ptr[k] <= j && tot_w - dist[k][ptr[k]] >= dist[k][ptr[k]]) ++ptr[k];
                mx = max(mx, pref_maxA[k][ptr[k]-1]);
                int l = ptr[k];
                int r = j;
                if (r >= l) {
                    mx = max(mx, query_sparse(k, l, r)+tot_w);
                }
                if (k != i)
                    upd_pr(k);
                if (k != j)
                    upd_suf(k);
            }
            mx = max<int64_t>(mx, furthest_pref[i] + furthest_suf[j] + min<int64_t>(c, dist[i][j]));
            // cout << i << " " << j << ": " << mx << "\n";
            res = min(res, mx);
        }
    }
    return res;
}

Compilation message (stderr)

shortcut.cpp: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