Submission #1152764

#	Time	Username	Problem	Language	Result	Execution time	Memory
1152764		irmuun	Marathon Race 2 (JOI24_ho_t3)	C++20	100 / 100	134 ms	33424 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define pb push_back
#define ff first
#define ss second
#define all(s) s.begin(),s.end()
#define rall(s) s.rbegin(),s.rend()

void chmin(ll &a,ll b){a=min(a,b);}
void chmax(ll &a,ll b){a=max(a,b);}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    ll n,L;
    cin>>n>>L;
    ll x[n+5];
    for(ll i=1;i<=n;i++){
        cin>>x[i];
    }
    sort(x+1,x+n+1);
    ll m=0;
    ll X[n+5],cnt[n+5];
    x[0]=-1;
    for(ll i=1;i<=n;i++){
        if(x[i]!=x[i-1]){
            X[++m]=x[i];
            cnt[m]=1;
        }
        else{
            cnt[m]++;
        }
    }
    if(m>1000){
        ll q;
        cin>>q;
        while(q--){
            ll s,g,t;
            cin>>s>>g>>t;
            cout<<"No\n";
        }
        return 0;
    }
    vector<ll>v,u;
    for(ll i=1;i<=m;i++){
        v.pb(X[i]);
        u.pb(X[i]);
    }
    reverse(all(u));
    ll pre[m+5],suf[m+5];
    pre[0]=0;
    suf[0]=0;
    for(ll i=1;i<=m;i++){
        pre[i]=pre[i-1]+cnt[i];
    }
    reverse(cnt+1,cnt+m+1);
    for(ll i=1;i<=m;i++){
        suf[i]=suf[i-1]+cnt[i];
    }
    reverse(cnt+1,cnt+m+1);
    ll dp[2][m+5][m+5][2];
    for(ll k=0;k<2;k++){
        for(ll i=0;i<=m;i++){
            for(ll j=0;j<=m;j++){
                dp[k][i][j][0]=dp[k][i][j][1]=(ll)1e18;
            }
        }
        if(k==0) dp[k][1][0][0]=0;
        else dp[k][0][1][1]=0;
        for(ll i=0;i<=(ll)v.size();i++){
            for(ll j=0;j<=(ll)u.size();j++){
                if(i<(ll)v.size()){
                    ll pos=(i==0?v[i]:v[i-1]);
                    chmin(dp[k][i+1][j][0],dp[k][i][j][0]+abs(v[i]-pos)*(pre[i]+suf[j]+1));
                    pos=(j==0?u[j]:u[j-1]);
                    chmin(dp[k][i+1][j][0],dp[k][i][j][1]+abs(v[i]-pos)*(pre[i]+suf[j]+1));
                }
                if(j<(ll)u.size()){
                    ll pos=(i==0?v[i]:v[i-1]);
                    chmin(dp[k][i][j+1][1],dp[k][i][j][0]+abs(u[j]-pos)*(pre[i]+suf[j]+1));
                    pos=(j==0?u[j]:u[j-1]);
                    chmin(dp[k][i][j+1][1],dp[k][i][j][1]+abs(u[j]-pos)*(pre[i]+suf[j]+1));
                }
            }
        }
    }
    ll q;
    cin>>q;
    while(q--){
        ll s,g,t;
        cin>>s>>g>>t;
        ll L=upper_bound(X+1,X+m+1,g)-X-1;//# of left is l
        ll R=m-L;
        //k=0 start from left, k=1 start from right
        ll ans=(ll)1e18;
        if(L>0) chmin(ans,dp[0][L][R][0]+abs(s-X[1])+abs(g-X[L])*(n+1));
        if(R>0) chmin(ans,dp[1][L][R][1]+abs(s-X[m])+abs(g-X[L+1])*(n+1));
        if(L>0&&R>0){
            chmin(ans,dp[0][L][R][1]+abs(s-X[1])+abs(g-X[L+1])*(n+1));
            chmin(ans,dp[1][L][R][0]+abs(s-X[m])+abs(g-X[L])*(n+1));
        }
        //add N
        ans+=n;
        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