Submission #1240212

#	Time	Username	Problem	Language	Result	Execution time	Memory
1240212		rythm_of_knight	Marathon Race 2 (JOI24_ho_t3)	C++17	100 / 100	741 ms	41096 KiB

Main

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

const ll N = 5e5 + 5, K = 1415;
ll a[N], dp[K][K][2], ds[K][K][2], pr[K], sf[K];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    ll n, l;
    cin >> n >> l;
    vector <ll> x(1), prf(1);
    for (ll i = 1; i <= n; i++) {
        ll b;
        cin >> b;
        a[b]++;
    }
    ll tmp = 0;
    for (ll i = 0; i < N; i++)
        if (a[i])
            tmp += a[i], x.push_back(i), prf.push_back(tmp);
    ll cnt = n + 1, cur = 1;
    n = x.size(); n--;
    if (n < K) {
        for (ll i = 1; i <= n; i++)
            for (ll j = 1; j <= n; j++)
                for (ll k = 0; k < 2; k++)
                    dp[i][j][k] = ds[i][j][k] = N;
        dp[1][n][0] = ds[1][n][1] = 0;
        dp[1][n][1] = ds[1][n][0] = x[n] - x[1];
        for (ll add = n - 2; add >= 0; add--) {
            for (ll l = 1; l + add <= n; l++) {
                ll r = l + add, res = 0;
                if (l > 1) {
                    dp[l][r][0] = dp[l - 1][r][0];
                    cur = cnt - prf[r] + prf[l - 2];
                    res += a[x[l - 1]];
                    cur += a[x[l - 1]];
                    res += (x[l] - x[l - 1]) * cur;
                    res = min(res, N);
                    dp[l][r][0] += res;
                }
                res = 0;
                if (r < n) {
                    dp[l][r][1] = dp[l][r + 1][1];
                    cur = cnt - prf[r + 1] + prf[l - 1];
                    res += a[x[r + 1]];
                    cur += a[x[r + 1]];
                    res += (x[r + 1] - x[r]) * cur;
                    res = min(res, N);
                    dp[l][r][1] += res;
                }
                dp[l][r][0] = min(dp[l][r][0], dp[l][r][1] + (x[r] - x[l]) * (cnt - prf[r] + prf[l - 1]));
                dp[l][r][1] = min(dp[l][r][1], dp[l][r][0] + (x[r] - x[l]) * (cnt - prf[r] + prf[l - 1]));
            }
        }
        for (ll add = n - 2; add >= 0; add--) {
            for (ll l = 1; l + add <= n; l++) {
                ll r = l + add, res = 0;
                if (l > 1) {
                    ds[l][r][0] = ds[l - 1][r][0];
                    cur = cnt - prf[r] + prf[l - 2];
                    res += a[x[l - 1]];
                    cur += a[x[l - 1]];
                    res += (x[l] - x[l - 1]) * cur;
                    res = min(res, N);
                    ds[l][r][0] += res;
                }
                res = 0;
                if (r < n) {
                    ds[l][r][1] = ds[l][r + 1][1];
                    cur = cnt - prf[r + 1] + prf[l - 1];
                    res += a[x[r + 1]];
                    cur += a[x[r + 1]];
                    res += (x[r + 1] - x[r]) * cur;
                    res = min(res, N);
                    ds[l][r][1] += res;
                }
                ds[l][r][0] = min(ds[l][r][0], ds[l][r][1] + (x[r] - x[l]) * (cnt - prf[r] + prf[l - 1]));
                ds[l][r][1] = min(ds[l][r][1], ds[l][r][0] + (x[r] - x[l]) * (cnt - prf[r] + prf[l - 1]));
            }
        }
        for (ll i = 1; i <= n; i++)
            pr[i] = min(dp[i][i][0], dp[i][i][1]) + a[x[i]];
        for (ll i = 1; i <= n; i++)
            sf[i] = min(ds[i][i][0], ds[i][i][1]) + a[x[i]];
        // for (ll i = 1; i <= n; i++)
        //     cout << pr[i] << ' ';
        // cout << '\n';
        // for (ll i = 1; i <= n; i++)
        //     cout << sf[i] << ' ';
        // cout << '\n';
    }
    ll q;
    cin >> q;
    while (q--) {
        ll s, g, t;
        cin >> s >> g >> t;
        if (n >= K) {
            cout << "No\n";
            continue;
        }
        ll ans = N;
        for (ll i = 1; i <= n; i++)
            ans = min(ans, min(llabs(s - x[1]) + pr[i], llabs(s - x[n]) + sf[i]) + 1ll * cnt * llabs(g - x[i]));
        // cout << ans << ' ';
        if (ans <= t)
            cout << "Yes\n";
        else
            cout << "No\n";
    }
}

• Subtask 1: 7 / 7
• Subtask 2: 7 / 7
• Subtask 3: 10 / 10
• Subtask 4: 28 / 28
• Subtask 5: 10 / 10
• Subtask 6: 19 / 19
• Subtask 7: 19 / 19