Submission #1177035

#	Time	Username	Problem	Language	Result	Execution time	Memory
1177035		MongHwa	Bitaro's travel (JOI23_travel)	C++20	0 / 100	70 ms	6468 KiB

travel

#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unroll-loops")
#include <iostream>
#include <algorithm>
using namespace std;

#define ll long long
#define INF 1e17

ll arr[200005], psum[200005];
ll dp[200005];

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n;
    cin >> n;

    for(int i = 1; i <= n; i++)
    {
        cin >> arr[i];
        psum[i] = psum[i-1] + arr[i];
    }

    dp[1] = dp[n] = arr[n]-arr[1];
    for(int i = 2; i < n; i++)
    {
        int l = i-1, r = i+1, pos = i;
        while(1)
        {
            if(l == 0 || r == n+1)
            {
                dp[i] += dp[1];
                break;
            }
            else if(arr[pos]-arr[l] > 100)
            {
                dp[i] += (arr[n]-arr[pos]+dp[1]);
                break;
            }
            else if(arr[r]-arr[pos] > 100)
            {
                dp[i] += (arr[pos]-arr[1]+dp[1]);
                break;
            }

            if(arr[pos]-arr[l] <= arr[r]-arr[pos])
            {
                dp[i] += (arr[pos]-arr[l]);
                pos = l;
                l--;
            }
            else
            {
                dp[i] += (arr[r]-arr[pos]);
                pos = r;
                r++;
            }
        }
    }

    int q;
    cin >> q;
    while(q--)
    {
        int x;
        cin >> x;

        int it = lower_bound(arr+1, arr+n+1, x) - arr;
        if(arr[it] == x)
            cout << dp[it] << '\n';
        else
        {
            ll ans = INF;
            if(it > 1)
                ans = min(ans, dp[it-1]+abs(x-arr[it-1]));
            if(it < n+1)
                ans = min(ans, dp[it]+abs(x-arr[it]));
            cout << ans << '\n';
        }
    }
}

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