제출 #1352068

#제출 시각아이디문제언어결과실행 시간메모리
1352068gayMarathon Race 2 (JOI24_ho_t3)C++20
0 / 100
598 ms1114112 KiB
#include <bits/stdc++.h>
#include <experimental/random>
#include <random>

//#include <ext/pb_ds/assoc_container.hpp>
//using namespace __gnu_pbds;

using namespace std;

using ld = long double;
using ll = long long;

const ll INF = 1e18, MOD = 1e9 + 7;

void solve();

signed main() {
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0);
    int q = 1;
    //cin >> q;
    while (q--) {
        solve();
    }
}

void solve() {
    ll n, l;
    cin >> n >> l;
    vector<ll> cnt(l + 1);
    ll mn = INF, mx = -INF;
    for (int i = 0; i < n; i++) {
        ll x; cin >> x;
        cnt[x]++;
        mn = min(mn, x), mx = max(mx, x);
    }
    vector<ll> pref = {0};
    for (auto c : cnt) {
        pref.push_back(pref.back() + c);
    }
    vector<vector<vector<ll>>> dp1(l + 1, vector<vector<ll>>(l + 1, vector<ll>(2, INF)));
    vector<vector<vector<ll>>> dp2(l + 1, vector<vector<ll>>(l + 1, vector<ll>(2, INF)));
    dp1[mn][mx][0] = 0;
    dp2[mn][mx][1] = 0;
    for (ll len = mx - mn; len > 0; len--) {
        for (ll lf = mn; lf + len <= mx; lf++) {
            ll rf = lf + len;
            ll col = n - pref[rf + 1] + pref[lf] + 1;
            dp1[lf + 1][rf][0] = dp1[lf][rf][0] + (col + cnt[lf]);
            dp1[lf][rf - 1][1] = dp1[lf][rf][0] + (rf - lf) * col + (col + cnt[rf]);
            dp1[lf + 1][rf][0] = min(dp1[lf + 1][rf][0], dp1[lf][rf][1] + (rf - lf) * col + (col + cnt[lf]));
            dp1[lf][rf - 1][1] = min(dp1[lf][rf - 1][1], dp1[lf][rf][1] + (col + cnt[rf]));

            dp2[lf + 1][rf][0] = dp2[lf][rf][0] + (col + cnt[lf]);
            dp2[lf][rf - 1][1] = dp2[lf][rf][0] + (rf - lf) * col + (col + cnt[rf]);
            dp2[lf + 1][rf][0] = min(dp2[lf + 1][rf][0], dp2[lf][rf][1] + (rf - lf) * col + (col + cnt[lf]));
            dp2[lf][rf - 1][1] = min(dp2[lf][rf - 1][1], dp2[lf][rf][1] + (col + cnt[rf]));
        }
    }

    ll q; cin >> q;
    while (q--) {
        ll s, g, t;
        cin >> s >> g >> t;
        t -= n;
        ll ans = INF;
        for (int x = 0; x <= l; x++) {
            ans = min(ans, abs(s - mn) + min(dp1[x][x][0], dp1[x][x][1]) + abs(x - g) * (n + 1));
            ans = min(ans, abs(s - mx) + min(dp2[x][x][0], dp2[x][x][1]) + abs(x - g) * (n + 1));
        }
        if (ans <= t) {
            cout << "Yes\n";
        } else {
            cout << "No\n";
        }
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...