제출 #1197430

#제출 시각아이디문제언어결과실행 시간메모리
1197430NewtonabcMarathon Race 2 (JOI24_ho_t3)C++20
52 / 100
18 ms36516 KiB
#include<bits/stdc++.h> #define int long long using namespace std; const int N=1e3+10; const int M=5e5+10; int a[M]; // time used that have kept the i left balls and j right balls recent direction is (left/right=0/1) int dpl[N][N][2],dpr[N][N][2],qs[N]; map<int,int> mp; signed main(){ int n,l; cin>>n >>l; for(int i=1;i<=n;i++){ cin>>a[i]; mp[a[i]]++; } vector<pair<int,int>> v; for(auto it:mp){ v.push_back({it.first,it.second}); } int m=v.size(); for(int i=0;i<=m;i++) for(int j=0;j<=m;j++) for(int k=0;k<2;k++) dpl[i][j][k]=dpr[i][j][k]=1e9; qs[0]=v[0].second; for(int i=1;i<m;i++) qs[i]=qs[i-1]+v[i].second; dpl[1][0][0]=0; dpr[0][1][1]=0; for(int i=0;i<=m;i++){ for(int j=0;j<=m;j++){ if(i+j>m) continue; int ball=qs[i-1]+qs[m-1]-qs[m-j-1]; if(i-2>=0) dpl[i][j][0]=min(dpl[i][j][0],dpl[i-1][j][0]+((ball-v[i-1].second+1)*(v[i-1].first-v[i-2].first))); if(i-1>=0 && m-j<=m-1) dpl[i][j][0]=min(dpl[i][j][0],dpl[i-1][j][1]+((ball-v[i-1].second+1)*(v[m-j].first-v[i-1].first))); if(j-1>=0 && i-1>=0 && m-j<=m-1) dpl[i][j][1]=min(dpl[i][j][1],dpl[i][j-1][0]+((ball-v[m-j].second+1)*(v[m-j].first-v[i-1].first))); if(m-j+1<=m-1 && j-1>=0 && m-j<=m-1) dpl[i][j][1]=min(dpl[i][j][1],dpl[i][j-1][1]+((ball-v[m-j].second+1)*(v[m-j+1].first-v[m-j].first))); if(i-2>=0) dpr[i][j][0]=min(dpr[i][j][0],dpr[i-1][j][0]+((ball-v[i-1].second+1)*(v[i-1].first-v[i-2].first))); if(i-1>=0 && m-j<=m-1) dpr[i][j][0]=min(dpr[i][j][0],dpr[i-1][j][1]+((ball-v[i-1].second+1)*(v[m-j].first-v[i-1].first))); if(j-1>=0 && i-1>=0 && m-j<=m-1) dpr[i][j][1]=min(dpr[i][j][1],dpr[i][j-1][0]+((ball-v[m-j].second+1)*(v[m-j].first-v[i-1].first))); if(m-j+1<=m-1 && j-1>=0 && m-j<=m-1) dpr[i][j][1]=min(dpr[i][j][1],dpr[i][j-1][1]+((ball-v[m-j].second+1)*(v[m-j+1].first-v[m-j].first))); } } //cout<<dpr[0][2][0] <<"\n"; int q; cin>>q; while(q--){ int a,b,c; cin>>a >>b >>c; if(m>=1000){ cout<<"No\n"; continue; } int l=upper_bound(v.begin(),v.end(),make_pair(b,LLONG_MIN))-v.begin(); int r=m-l; //cout<<l <<" " <<r <<"\n"; int ans=INT_MAX; if(l!=0){ int st=abs(a-v[0].first); //cout<<st <<" " <<dpl[l][m-l][0] <<" " <<(n+1LL)*(b-v[l-1].first) <<" " <<(b-v[l-1].first) <<"\n"; ans=min(ans,st+dpl[l][m-l][0]+(n+1LL)*(b-v[l-1].first)); if(r!=0) ans=min(ans,st+dpl[l][m-l][1]+(n+1LL)*(v[l].first-b)); } if(r!=0){ int st=abs(v[m-1].first-a); if(l!=0) ans=min(ans,st+dpr[l][m-l][0]+(n+1LL)*(b-v[l-1].first)); ans=min(ans,st+dpr[l][m-l][1]+(n+1LL)*(v[l].first-b)); } ans+=n; if(ans<=c) cout<<"Yes\n"; else cout<<"No\n"; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...