Submission #1231539

#	Time	Username	Problem	Language	Result	Execution time	Memory
1231539		TadijaSebez	Marathon Race 2 (JOI24_ho_t3)	C++20	100 / 100	303 ms	28524 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back

const int N=500050;
int x[N],n;

const ll inf=1e18;

const int M=1005;
ll dp[2][M][M][2];
int sum[M][M];

vector<pair<int,int>> pts;

ll DP(int from,int l,int r,int now){
    ll& curDp=dp[from][l][r][now];
    if(curDp!=-1){
        return curDp;
    }
    curDp=inf;
    int pos=now==0?pts[l].first:pts[r].first;
    if(l!=0){
        ll tmp=DP(from,l-1,r,0)+(ll)(sum[l][r]+1)*abs(pts[l-1].first-pos);
        if(curDp>tmp){
            curDp=tmp;
        }
    }
    if(r+1!=pts.size()){
        ll tmp=DP(from,l,r+1,1)+(ll)(sum[l][r]+1)*abs(pts[r+1].first-pos);
        if(curDp>tmp){
            curDp=tmp;
        }
    }
    if(now==0)curDp+=pts[l].second;
    else curDp+=pts[r].second;
    //printf("from:%i l:%i r:%i now:%i dp:%lld\n",from,l,r,now,curDp);
    return curDp;
}

bool largeN=false;
bool Query(int s,int g,int t){
    if(largeN)return false;
    ll mn=inf;
    int j=lower_bound(pts.begin(),pts.end(),make_pair(g,0))-pts.begin();
    for(int i=max(0,j-10);i<min(j+10,(int)pts.size());i++){
    //for(int i=0;i<pts.size();i++){
        mn=min(mn,min(dp[0][i][i][0],dp[0][i][i][1])+(ll)abs(pts[i].first-g)*(n+1)+abs(pts[0].first-s));
        mn=min(mn,min(dp[1][i][i][0],dp[1][i][i][1])+(ll)abs(pts[i].first-g)*(n+1)+abs(pts.back().first-s));
    }
    //printf("mn: %lld\n",mn);
    return mn<=t;
}
int main(){
    int l;
    scanf("%i %i",&n,&l);
    map<int,int> cnt;
    for(int i=1;i<=n;i++){
        scanf("%i",&x[i]);
        cnt[x[i]]++;
    }
    pts=vector<pair<int,int>>(cnt.begin(),cnt.end());
    if(pts.size()<M){
        int sz=pts.size();

        for(int i=0;i<sz;i++){
            sum[i][i]=n-pts[i].second;
            for(int j=i+1;j<sz;j++){
                sum[i][j]=sum[i][j-1]-pts[j].second;
            }
        }

        for(int i=0;i<sz;i++){
            for(int j=i;j<sz;j++){
                dp[0][i][j][0]=-1;
                dp[0][i][j][1]=-1;
                dp[1][i][j][0]=-1;
                dp[1][i][j][1]=-1;
            }
        }
        dp[0][0][sz-1][0]=pts[0].second;
        dp[0][0][sz-1][1]=inf;
        dp[1][0][sz-1][0]=inf;
        dp[1][0][sz-1][1]=pts.back().second;
        for(int i=0;i<sz;i++){
            DP(0,i,i,0);
            DP(0,i,i,1);
            DP(1,i,i,0);
            DP(1,i,i,1);
        }
    }else{
        largeN=true;
    }
    int q;
    scanf("%i",&q);
    while(q--){
        int s,g,t;
        scanf("%i %i %i",&s,&g,&t);
        printf(Query(s,g,t)?"Yes\n":"No\n");
    }
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:57:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   57 |     scanf("%i %i",&n,&l);
      |     ~~~~~^~~~~~~~~~~~~~~
Main.cpp:60:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   60 |         scanf("%i",&x[i]);
      |         ~~~~~^~~~~~~~~~~~
Main.cpp:96:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   96 |     scanf("%i",&q);
      |     ~~~~~^~~~~~~~~
Main.cpp:99:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   99 |         scanf("%i %i %i",&s,&g,&t);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~

• 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