Submission #1321663

#TimeUsernameProblemLanguageResultExecution timeMemory
1321663exoworldgdSoccer (JOI17_soccer)C++20
100 / 100
1139 ms20668 KiB
#include<bits/stdc++.h> #define exoworldgd cin.tie(0)->sync_with_stdio(0),cout.tie(0) #define int long long using namespace std; const int INF=1e18,MX=600; int h,w,a,b,c,n,pref[505][505],dp[505][505],g1[505],g2[505],s[100005][2]; signed main(void){ exoworldgd; cin>>h>>w>>a>>b>>c>>n,h++,w++; for(int i=0;i<h;i++)for(int j=0;j<w;j++)pref[i][j]=INF; for(int i=0;i<n;i++)cin>>s[i][0]>>s[i][1],pref[s[i][0]][s[i][1]]=0; if(c<=a){cout<<(abs(s[0][0]-s[n-1][0])+abs(s[0][1]-s[n-1][1]))*c;return 0;} set<array<int,2>>st; for(int i=0;i<n;i++)st.insert({0,s[i][0]*w+s[i][1]}); for(int i,j;st.size();){ i=st.begin()->at(1)/w,j=st.begin()->at(1)%w,st.erase(st.begin()); for(int ij=max(0LL,j-1);ij<min(j+2,w);ij++)if(pref[i][ij]>pref[i][j]+abs(ij-j)*c)st.erase({pref[i][ij],i*w+ij}),pref[i][ij]=pref[i][j]+abs(ij-j)*c,st.insert({pref[i][ij],i*w+ij}); for(int ij=max(0LL,i-1);ij<min(i+2,h);ij++)if(pref[ij][j]>pref[i][j]+abs(ij-i)*c)st.erase({pref[ij][j],ij*w+j}),pref[ij][j]=pref[i][j]+abs(i-ij)*c,st.insert({pref[ij][j],ij*w+j}); } for(int i=0;i<h;i++)for(int j=0;j<w;j++)dp[i][j]=INF; dp[s[0][0]][s[0][1]]=0,st.insert({0,s[0][0]*w+s[0][1]}); while(st.size()){ int i=st.begin()->at(1)/w,j=st.begin()->at(1)%w; if(dp[s[n-1][0]][s[n-1][1]]<=c+st.begin()->at(0)&&dp[s[n-1][0]][s[n-1][1]]<=a+b+st.begin()->at(0)){cout<<dp[s[n-1][0]][s[n-1][1]];return 0;} st.erase(st.begin()); if(g1[i]<MX){ g1[i]++; for(int ij=0;ij<w;ij++)if(dp[i][ij]>dp[i][j]+abs(ij-j)*a+b+pref[i][ij])st.erase({dp[i][ij],i*w+ij}),dp[i][ij]=dp[i][j]+abs(ij-j)*a+b+pref[i][ij],st.insert({dp[i][ij],i*w+ij}); } if(g2[j]<MX){ g2[j]++; for(int ij=0;ij<h;ij++)if(dp[ij][j]>dp[i][j]+abs(ij-i)*a+b+pref[ij][j])st.erase({dp[ij][j],ij*w+j}),dp[ij][j]=dp[i][j]+abs(i-ij)*a+b+pref[ij][j],st.insert({dp[ij][j],ij*w+j}); } for(int ij=max(0LL,j-1);ij<min(j+2,w);ij++)if(dp[i][ij]>dp[i][j]+abs(ij-j)*c)st.erase({dp[i][ij],i*w+ij}),dp[i][ij]=dp[i][j]+abs(ij-j)*c,st.insert({dp[i][ij],i*w+ij}); for(int ij=max(0LL,i-1);ij<min(i+2,h);ij++)if(dp[ij][j]>dp[i][j]+abs(ij-i)*c)st.erase({dp[ij][j],ij*w+j}),dp[ij][j]=dp[i][j]+abs(i-ij)*c,st.insert({dp[ij][j],ij*w+j}); } cout<<dp[s[n-1][0]][s[n-1][1]]; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...