Submission #1150662

#	Time	Username	Problem	Language	Result	Execution time	Memory
1150662		alir3za_zar3	Marathon Race 2 (JOI24_ho_t3)	C++20	100 / 100	139 ms	21616 KiB

Main

// Alir3za.Zar3 -> Shiraz , Iran
#include <bits/stdc++.h>
using namespace std;
#define     int     long long

const int mxN = 1e3+7 , Inf = 2e18;
int n,L , x[mxN<<9] , joi;
int dp[2][mxN][mxN] , f[2][mxN] , px[mxN<<9];
vector<pair<int,int>> p;

void iN ()
{
    cin >> n >> L; joi=n;
    for (int i=1; i<=n; i++)
        cin >> x[i];
}

void compress ()
{
    sort(x+1,x+n+1);
    p.push_back( { x[1] , 0 } );
    for (int i=1; i<=n; i++)
    {
        if (p.back().first == x[i]) 
            p.back().second++;
        else p.push_back( { x[i] , 1 } );
        px[ x[ i ] ]++;
    }
    n = p.size();
    for (int i=1; i<(mxN<<9); i++)
        px[i] += px[i-1];
}

void fill_dp ()
{
    if (n >= mxN) return;

    for (int T=0; T<2; T++)
    {
        for (int l=0; l<n; l++)
            for (int r=0; r<n; r++)
                dp[0][l][r] = dp[1][l][r] = Inf;
        dp[T][0][n-1] = 0;

        for (int len = n; len>1; len--)
            for (int l=0 , r=len-1; r<n; l++,r++)
            {
                int ball = joi + px[ p[l].first-1 ] - px[ p[r].first ] + 1;

                dp[0][l+1][r] = min( dp[0][l+1][r] , dp[0][l][r] + (ball + p[l].second)*(p[l+1].first-p[l].first) );
                dp[0][l+1][r] = min( dp[0][l+1][r] , dp[1][l][r] + ball*(p[r].first+p[l+1].first-2*p[l].first) + p[l].second*(p[l+1].first-p[l].first) );

                dp[1][l][r-1] = min( dp[1][l][r-1] , dp[1][l][r] + (ball + p[r].second)*(p[r].first-p[r-1].first));
                dp[1][l][r-1] = min( dp[1][l][r-1] , dp[0][l][r] + ball*(2*p[r].first-p[l].first-p[r-1].first) + p[r].second*(p[r].first-p[r-1].first) );
            }

        for (int i=0; i<n; i++)
            f[T][i] = min(dp[0][i][i] , dp[1][i][i]);
    }
}

void ouT ()
{
    int q; cin >> q;
    while (q--)
    {
        int st , en , T;
        cin >> st >> en >> T;
        T -= joi;
        if (n >= mxN) 
        {
            cout << "No\n";
            continue;
        }
        int k = lower_bound(p.begin(),p.end(),make_pair(en,0ll))-p.begin();
        int out = Inf;
        for (int i=max(0ll , k-2); i<=min(n-1 , k+2); i++)
        {
            out = min( out , f[0][i] + abs(st-p[0].first) + (joi+1)*abs(en-p[i].first) );
            out = min( out , f[1][i] + abs(st-p[n-1].first) + (joi+1)*abs(en-p[i].first) );
        }
        if (out <= T)
            cout << "Yes\n";
        else 
            cout << "No\n";
    }
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);     cout.tie(0);

    iN ();
    compress ();
    fill_dp ();
    ouT ();
}

• 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