Submission #894623

#TimeUsernameProblemLanguageResultExecution timeMemory
894623pccSoccer (JOI17_soccer)C++14
100 / 100
2554 ms24336 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> #define int ll const int mxn = 550; const ll inf = 4e18; 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}}; ll lu[mxn][mxn],rd[mxn][mxn],ru[mxn][mxn],ld[mxn][mxn]; bitset<mxn> inq[mxn]; queue<pii> q; int lim = 2.95*CLOCKS_PER_SEC; int st; main(){ ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); for(auto &i:lu)for(auto &j:i)j = inf;//r+c+lu[r][c] for(auto &i:rd)for(auto &j:i)j = inf; for(auto &i:ru)for(auto &j:i)j = inf; for(auto &i:ld)for(auto &j:i)j = inf; for(auto &i:player)for(auto &j:i)j = inf; for(auto &i:dp)for(auto &j:i)j = inf; st = clock(); cin>>N>>M>>A>>B>>C>>K; N++,M++; for(int i = 0;i<K;i++){ int r,c; cin>>arr[i].fs>>arr[i].sc; arr[i].fs++,arr[i].sc++; r = arr[i].fs,c = arr[i].sc; lu[r][c] = min(lu[r][c],-r-c); ld[r][c] = min(ld[r][c],r-c); ru[r][c] = min(ru[r][c],c-r); rd[r][c] = min(rd[r][c],r+c); } for(int i = 1;i<=N;i++)for(int j = 1;j<=M;j++)lu[i][j] = min({lu[i][j],lu[i-1][j],lu[i][j-1]}); for(int i = N;i>=1;i--)for(int j = M;j>=1;j--)rd[i][j] = min({rd[i][j],rd[i+1][j],rd[i][j+1]}); for(int i = 1;i<=N;i++)for(int j = M;j>=1;j--)ru[i][j] = min({ru[i][j],ru[i-1][j],ru[i][j+1]}); for(int i = N;i>=1;i--)for(int j = 1;j<=M;j++)ld[i][j] = min({ld[i][j],ld[i+1][j],ld[i][j-1]}); for(int i = 1;i<=N;i++){ for(int j = 1;j<=M;j++){ player[i][j] = min({i+j+lu[i][j],-i-j+rd[i][j],-i+j+ld[i][j],i-j+ru[i][j]}); } } dp[arr[0].fs][arr[0].sc] = 0; inq[arr[0].fs][arr[0].sc] = true; q.push(arr[0]); while(!q.empty()&&clock()-st<=lim){ auto tt = q.front(); q.pop(); int r = tt.fs,c = tt.sc; inq[r][c] = false; //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; if(!inq[nr][nc])inq[nr][nc] = true,q.push({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]; if(!inq[nr][nc])inq[nr][nc] = true,q.push({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-1].fs][arr[K-1].sc]; }

Compilation message (stderr)

soccer.cpp:26:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   26 | main(){
      | ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...