Submission #1152520

#	Time	Username	Problem	Language	Result	Execution time	Memory
1152520		irmuun	Marathon Race 2 (JOI24_ho_t3)	C++20	81 / 100	508 ms	1114112 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);
    vector<ll>v,u;
    for(ll i=1;i<=n;i++){
        v.pb(x[i]);
        u.pb(x[i]);
    }
    reverse(all(u));
    ll dp[2][n+5][n+5][2];
    for(ll k=0;k<2;k++){
        for(ll i=0;i<=n;i++){
            for(ll j=0;j<=n;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)*(i+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)*(i+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)*(i+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)*(i+j+1));
                }
            }
        }
    }
    ll q;
    cin>>q;
    while(q--){
        ll s,g,t;
        cin>>s>>g>>t;
        ll L=upper_bound(x+1,x+n+1,g)-x-1;//# of left is l
        ll R=n-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[n])+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[n])+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: 0 / 19