Submission #894552

#TimeUsernameProblemLanguageResultExecution timeMemory
894552pccSoccer (JOI17_soccer)C++14
0 / 100
93 ms7236 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define pll pair<ll,ll> #define pii pair<int,int> #define fs first #define sc second #define tlll tuple<ll,ll,ll> const int mxn = 550; const ll inf = 1e18; int N,M,K,A,B,C; ll dp[mxn][mxn]; ll player[mxn][mxn]; pll arr[mxn*mxn]; priority_queue<tlll,vector<tlll>,greater<tlll>> pq; pii dir[] = {{0,1},{0,-1},{1,0},{-1,0}}; int main(){ ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); cin>>N>>M>>A>>B>>C>>K; for(int i = 1;i<=K;i++)cin>>arr[i].fs>>arr[i].sc; for(auto &i:player)for(auto &j:i)j = inf; for(int i = 0;i<=N;i++)for(int j = 0;j<=M;j++){ for(int k = 1;k<=K;k++){ player[i][j] = min(player[i][j],abs(arr[k].fs-i)+abs(arr[k].sc-j)); } } for(auto &i:dp)for(auto &j:i)j = inf; dp[arr[1].fs][arr[1].sc] = 0; pq.push(make_tuple(0,arr[1].fs,arr[1].sc)); while(!pq.empty()){ auto tt = pq.top(); pq.pop(); int r = get<1>(tt),c = get<2>(tt),ds = get<0>(tt); if(ds != dp[r][c])continue; //cout<<r<<' '<<c<<":"<<ds<<endl; for(auto &d:dir){ int nr = r+d.fs,nc = c+d.sc; if(nr<0||nr>N||nc<0||nc>M)continue; if(dp[nr][nc]>dp[r][c]+C){ dp[nr][nc] = dp[r][c]+C; pq.push(make_tuple(dp[nr][nc],nr,nc)); } nr = r+d.fs,nc = c+d.sc; int pt = 1; while(nr>=0&&nr<=N&&nc>=0&&nc<=M){ if(dp[nr][nc]>dp[r][c]+A*pt+B+C*player[nr][nc]){ dp[nr][nc] = dp[r][c]+A*pt+B+C*player[nr][nc]; pq.push(make_tuple(dp[nr][nc],nr,nc)); } pt++; nr += d.fs,nc += d.sc; } } } /* for(int i = 0;i<=N;i++){ for(int j = 0;j<=M;j++)cout<<setw(3)<<dp[i][j]<<' '; cout<<endl; } */ cout<<dp[arr[K].fs][arr[K].sc]; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...