Submission #1311641

#	Time	Username	Problem	Language	Result	Execution time	Memory
1311641		Marceantasy	Marathon Race 2 (JOI24_ho_t3)	C++20	100 / 100	140 ms	31704 KiB

Main

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ar array
#define rep(i, n) for (ll i = 0; i < (int)n; ++i)

// mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

const int mxN = 1e3+5, M = 998244353;
ll dp[mxN][mxN][2], sm[mxN];
ll cL[mxN][mxN], cR[mxN][mxN];
ll opt[mxN][2];
ll n, z, m, q;

void solve(){
    cin >> n >> z;
    vector<ll> b(n);
    rep(i, n) cin >> b[i];
    sort(b.begin(), b.end());
    vector<ar<ll, 2>> a;
    for(ll i=0; i<n; ){
        ll j = i;
        while(j < n && b[i] == b[j]) j++;
        a.push_back({b[i], j-i});
        i = j;
    }
    m = n;
    n = a.size();
    
    cin >> q;
    if(n > 1000){
        while(q--) cout << "No\n";
        return;
    }
    rep(i, n) sm[i+1] = sm[i] + a[i][1];
    memset(opt, 0x3f, sizeof(opt));
    
    rep(k, 2){
        memset(dp, 0x3f, sizeof(dp));
        dp[0][n-1][k] = 0;
        for(ll i = n-1; i >= 0; --i){
            for(ll j = 0; j+i < n; ++j){
                ll s = j, e = j+i;
                ll tot = m + 1 - (sm[e+1] - sm[s]);
                if(s > 0){
                    ll cst = (a[e][0] - a[s-1][0]) * tot;
                    dp[s][e][1] = cst + cL[s-1][e];
                }
                if(e+1 < n){
                    ll cst = (a[e+1][0] - a[s][0]) * tot;
                    dp[s][e][0] = cst + cR[s][e+1];
                }
                cL[s][e] = dp[s][e][0];
                cR[s][e] = dp[s][e][1];
                if(s > 0){
                    cL[s][e] = min(cL[s][e], cL[s-1][e] + tot * (a[s][0]-a[s-1][0]));
                }if(e+1 < n){
                    cR[s][e] = min(cR[s][e], cR[s][e+1] + tot * (a[e+1][0]-a[e][0]));
                }
            }
        }
        rep(j, n) opt[j][k] = min(dp[j][j][0], dp[j][j][1]);
    }

    while(q--){
        ll s, e, x;
        cin >> s >> e >> x;
        ll ans = 1e18;
        ar<ll, 2> val = {e, -1};
        int idx = lower_bound(a.begin(), a.end(), val) - a.begin();
        for(int i = max(0, idx-3); i < min((int)n, idx+3); ++i){
            ans = min(ans, abs(a[i][0] - e) * (m+1) + m + opt[i][0] + abs(s - a[0][0]));
            ans = min(ans, abs(a[i][0] - e) * (m+1) + m + opt[i][1] + abs(s - a[n-1][0]));
        }
        cout << (ans <= x ? "Yes" : "No") << "\n";
    }
}


signed main(){
#ifdef _DEBUG
//	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
    std::ios_base::sync_with_stdio(false); std::cin.tie(0); std::cout.tie(0);

    int T = 1;

    // cin >> T;
    while (T--){
        solve();
    }
}

• 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