fork(2) download
copy 
  1. #include <cstdio>
  2. #include <iostream>
  3. #include <vector>
  4. #include <cstring>
  5. #include <queue>
  6. #define pb push_back
  7. #define rep(i,a,b) for (int i = (a);i<(b);i++)
  8.  
  9. using namespace std;
  10.  
  11. typedef long long ll;
  12.  
  13. const int maxh = 1e6 + 3;
  14. const int maxn = 1e3 + 3;
  15.  
  16. struct TCell
  17. {
  18.     int x,y,val;
  19.     TCell() : x(0),y(0),val(0) {};
  20.     TCell(int x_,int y_,int val_) : x(x_),y(y_),val(val_) {}; 
  21. };
  22.  
  23. struct cmp
  24. {
  25.     bool operator() (const TCell &a,const TCell &b) 
  26.     {
  27.         return a.val > b.val;
  28.     }
  29. };
  30.  
  31. int a[maxn][maxn],h[maxn][maxn];
  32. priority_queue<TCell,vector<TCell>,cmp> q;
  33. int m,n;
  34.  
  35. int dx[] = {1,0,-1,0};
  36. int dy[] = {0,1,0,-1};
  37.  
  38. bool inside(int x,int y)
  39. {
  40.     return !(x == m || y == n || x == 0-1 || y == 0-1);
  41. }
  42.  
  43. void dijkstra()
  44. {
  45.     rep(i,0,m) rep(j,0,n) h[i][j] = maxh;
  46.     rep(i,0,m)
  47.     {
  48.         h[i][0] = a[i][0];
  49.         h[i][n-1] = a[i][n-1];
  50.         q.push(TCell(i,0,h[i][0]));
  51.         q.push(TCell(i,n-1,h[i][n-1]));
  52.     } 
  53.     rep(i,1,n-1) 
  54.     {
  55.         h[0][i] = a[0][i];
  56.         h[m-1][i] = a[m-1][i];
  57.         q.push(TCell(0,i,a[0][i]));
  58.         q.push(TCell(m-1,i,a[m-1][i]));
  59.     }
  60.     while (! q.empty())
  61.     {
  62.         int x = q.top().x;
  63.         int y = q.top().y;
  64.         int d = q.top().val;
  65.         q.pop();
  66.         if (h[x][y] != d) continue;
  67.         rep(i,0,4)
  68.         {
  69.             int xk = x+dx[i];
  70.             int yk = y+dy[i];
  71.             if (inside(xk,yk))
  72.             {
  73.                 int nprio = max(a[xk][yk],d);
  74.                 if (h[xk][yk] > nprio)
  75.                 {
  76.                     h[xk][yk] = nprio;
  77.                     q.push(TCell(xk,yk,nprio));
  78.                 }
  79.             }
  80.         }
  81.     }
  82. }
  83.  
  84. int main()
  85. {
  86.     scanf("%d%d",&m,&n);
  87.     rep(i,0,m) rep(j,0,n) scanf("%d",&a[i][j]);
  88.     dijkstra();
  89.     ll ans = 0;
  90.     rep(i,0,m) rep(j,0,n) ans += h[i][j] - a[i][j];
  91.     printf("%lld",ans);
  92.     return 0;
  93. }
Success #stdin #stdout 0s 23096KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/s5EutH
language:
C++14 (clang 8.0)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!