Submission #1152369

#	Time	Username	Problem	Language	Result	Execution time	Memory
1152369		irmuun	Marathon Race 2 (JOI24_ho_t3)	C++20	0 / 100	0 ms	324 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);
    x[0]=0;
    ll q;
    cin>>q;
    while(q--){
        ll s,g,t;
        cin>>s>>g>>t;
        vector<ll>v,u;
        for(ll i=1;i<=n;i++){
            if(x[i]<g){
                v.pb(x[i]);
            }
            else{
                u.pb(x[i]);
            }
        }
        reverse(all(u));
        // for(ll x:v) cout<<x<<' ';
        // cout<<"\n";
        // for(ll x:u) cout<<x<<' ';
        // cout<<"\n";
        ll dp[n+5][n+5][2];
        for(ll i=0;i<=n;i++){
            for(ll j=0;j<=n;j++){
                dp[i][j][0]=dp[i][j][1]=(ll)1e18;
            }
        }
        dp[0][0][0]=dp[0][0][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()){//i,j to i+1,j
                    ll pos=(i==0?s:v[i-1]);
                    // ll pos1=(j==0?s:u[j-1]);
                    chmin(dp[i+1][j][0],dp[i][j][0]+abs(v[i]-pos)*(i+j+1));
                    pos=(j==0?s:u[j-1]);
                    chmin(dp[i+1][j][0],dp[i][j][1]+abs(v[i]-pos)*(i+j+1));
                }
                if(j<(ll)u.size()){
                    ll pos=(i==0?s:v[i-1]);
                    // ll pos1=(j==0?s:u[j-1]);
                    chmin(dp[i][j+1][1],dp[i][j][0]+abs(u[j]-pos)*(i+j+1));
                    pos=(j==0?s:u[j-1]);
                    chmin(dp[i][j+1][1],dp[i][j][1]+abs(u[j]-pos)*(i+j+1));
                }
            }
        }
        // for(ll i=0;i<=(ll)v.size();i++){
        //     for(ll j=0;j<=(ll)u.size();j++){
        //         cout<<dp[i][j][0]<<' '<<dp[i][j][1]<<' ';
        //     }
        //     cout<<"\n";
        // }
        ll tm=(ll)1e18;
        if(v.size()>0) chmin(tm,dp[v.size()][u.size()][0]+abs(v.back()-g)*(n+1));
        if(u.size()>0) chmin(tm,dp[v.size()][u.size()][1]+abs(u.back()-g)*(n+1));
        tm+=(n+1);//pick up time
        cout<<(tm<=t?"Yes":"No")<<"\n";
    }
}

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