Submission #1188503

#	Time	Username	Problem	Language	Result	Execution time	Memory
1188503		user736482	Marathon Race 2 (JOI24_ho_t3)	C++20	100 / 100	402 ms	38224 KiB

Main

#pragma GCC optimize("Ofast","unroll-loops","inline")
//#pragma GCC target("avx2")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define pb push_back
#define ff first
#define ss second
#define MOD 1000000009
#define INF 1000000019
#define INFL 1000000000000000099LL
#define POT (1<<20)
ll a,b,r,c,t,n,m,l,q,k,ak,ans,s;
map<ll,ll>mp;
vector<pair<ll,ll>>v,v2;
vector<ll> pref={0};
ll dp[1007][1007][2][2];

int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>n>>a;
    for(ll i=0;i<n;i++){
        cin>>a;
        mp[a]++;
    }
    for(auto it=mp.begin();it!=mp.end();it++){
        b++;
        v.pb((*it));
    }
    sort(v.begin(),v.end());
    for(pair<ll,ll>i : v){
        pref.pb(pref.back()+i.ss);
    }
    v2=v;
    reverse(v2.begin(),v2.end());
    if(b>1000){
        cin>>q;
        for(ll i=0;i<q;i++){
            cout<<"No"<<"\n";
        }
        return 0;
    }
    for(ll i=0;i<1007;i++){
        for(ll j=0;j<1007;j++){
            for(ll k=0;k<2;k++)
                for(ll p=0;p<2;p++)
                    dp[i][j][k][p]=INFL;
        }
    }
    dp[1][0][1][1]=v[0].ss;
    dp[0][1][0][0]=v2[0].ss;
    for(ll i=0;i<=v.size();i++){
        for(ll j=0;j+i<=v.size();j++){
            for(ll k=0;k<2;k++){
               
                if(i>1)
                dp[i][j][1][k]=min(dp[i][j][1][k],v[i-1].ss+dp[i-1][j][1][k]+abs(v[i-1].ff-v[i-2].ff)*(1+pref[i-1]+pref.back()-pref[pref.size()-1-j]));
                if(i&&j)
                dp[i][j][1][k]=min(dp[i][j][1][k],v[i-1].ss+dp[i-1][j][0][k]+abs(v[v.size()-j].ff-v[i-1].ff)*(1+pref[i-1]+pref.back()-pref[pref.size()-1-j]));
                if(j>1)
                dp[i][j][0][k]=min(dp[i][j][0][k],v2[j-1].ss+dp[i][j-1][0][k]+abs(v2[j-1].ff-v2[j-2].ff)*(1+pref[i]+pref.back()-pref[pref.size()-j]));
                if(j&&i)
                dp[i][j][0][k]=min(dp[i][j][0][k],v2[j-1].ss+dp[i][j-1][1][k]+abs(v2[v.size()-i].ff-v2[j-1].ff)*(1+pref[i]+pref.back()-pref[pref.size()-j]));
            }
        }
    }
    cin>>q;
    for(ll i=0;i<q;i++){
        cin>>a>>b>>c;
        ll pom=lower_bound(v.begin(),v.end(),(pair<ll,ll>){b,0})-v.begin();
        ll ans=INFL;
        if(pom!=v.size()){
        ans=min(ans,dp[pom][v.size()-pom][0][0]+abs(v.back().ff-a)+(n+1)*abs(v[pom].ff-b));
        ans=min(ans,dp[pom][v.size()-pom][0][1]+abs(v[0].ff-a)+(n+1)*abs(v[pom].ff-b));
            
        }
        if(pom){
        ans=min(ans,dp[pom][v.size()-pom][1][0]+abs(v.back().ff-a)+(n+1)*abs(v[pom-1].ff-b));
        ans=min(ans,dp[pom][v.size()-pom][1][1]+abs(v[0].ff-a)+(n+1)*abs(v[pom-1].ff-b));
            
        }
        if(ans<=c){
            cout<<"Yes\n";
        }
        else{
            cout<<"No\n";
        }
    }
    return 0;
}

• 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