Submission #1181714

#	Time	Username	Problem	Language	Result	Execution time	Memory
1181714		rythm_of_knight	Bitaro's travel (JOI23_travel)	C++17	0 / 100	48 ms	12356 KiB

travel

#include <bits/stdc++.h>
#define ar array
#define all(x) x.begin(), x.end()
using namespace std;
typedef long long ll;

const int N = 2e5 + 5;
map <ar <int, 3>, ll> mp;
ll x[N], n, ans[N];

ll rec(int l, int r, int now) {
    if (l == 1 && r == n)
        return 0;
    if (mp.count({l, r, now}))
        return mp[{l, r, now}];
    ll lf = 2e9, rg = 2e9;
    if (l > 1)
        lf = x[now] - x[l - 1];
    if (r < n)
        rg = x[r + 1] - x[now];
    if (lf <= rg)
        return mp[{l, r, now}] = rec(l - 1, r, l - 1) + lf;
    return mp[{l, r, now}] = rec(l, r + 1, r + 1) + rg;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> x[i];
    x[n + 1] = 2e9;
    for (int i = 1; i <= n; i++)
        ans[i] = rec(i, i, i);
    int q;
    cin >> q;
    while (q--) {
        int s;
        cin >> s;
        int l = lower_bound(x + 1, x + n + 2, s) - x - 1;
        int r = upper_bound(x + 1, x + n + 2, s) - x;
        ll lf = 2e9, rg = 2e9;
        if (l >= 1)
            lf = s - x[l];
        if (r <= n)
            rg = x[r] - s;
        if (lf <= rg)
            cout << ans[l] + lf << '\n';
        else
            cout << ans[r] + rg << '\n';
    }
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 10
• Subtask 3: 0 / 30
• Subtask 4: 0 / 55