fork(12) download 
  1. #include <fstream>
  2. #include <iostream>
  3. #include <queue>
  4. using namespace std;
  5.  
  6. typedef struct { int x,y,c,p; } node;
  7.  
  8. struct cmp_node
  9. {
  10.     bool operator () (node x,node y)
  11.     {
  12.         return x.c > y.c;
  13.     }
  14. };
  15.  
  16. node make_node(int x,int y,int c)
  17. {
  18.     node now;
  19.     now.x = x;
  20.     now.y = y;
  21.     now.c = c;
  22.     return now;
  23. }
  24.  
  25. node make_node(int x,int y,int c,int p)
  26. {
  27.     node now;
  28.     now.x = x;
  29.     now.y = y;
  30.     now.c = c;
  31.     now.p = p;
  32.     return now;
  33. }
  34.  
  35. ifstream F("volum.in");
  36. ofstream G("volum.out");
  37.  
  38. const int N = 760;
  39. const int infi = 1<<30;
  40.  
  41. int n,m,a[N][N],D[N][N];
  42. long long volume;
  43.  
  44. int dx[] = { 1 ,-1 , 0 , 0 , 0 };
  45. int dy[] = { 0 , 0 ,-1 , 1 , 0 };
  46.  
  47. bool inside(int x,int y)
  48. {
  49.     if ( x == 0 || y == 0 || x == n+1 || y == m+1 ) return 0;
  50.     return 1;
  51. }
  52.  
  53. void Bellman(int sx,int sy)
  54. {
  55.     queue<node> Q;
  56.  
  57.     D[sx][sy] = 0;
  58.     Q.push( make_node(sx,sy,D[sx][sy]) );
  59.  
  60.     while ( !Q.empty() )
  61.     {
  62.         while ( D[Q.front().x][Q.front().y] != Q.front().c )
  63.         {
  64.             Q.pop();
  65.             if ( Q.empty() ) break;
  66.         }
  67.         if ( Q.empty() ) break;
  68.  
  69.         node now = Q.front();
  70.         Q.pop();
  71.  
  72.         for (int d=0;d<4;++d)
  73.         {
  74.             int x = now.x+dx[d];
  75.             int y = now.y+dy[d];
  76.             if ( inside(x,y) )
  77.                 if ( D[x][y] > max( D[now.x][now.y] , a[x][y] ) )
  78.                 {
  79.                     D[x][y] = max( D[now.x][now.y] , a[x][y] );
  80.                     Q.push( make_node( x , y , max( D[now.x][now.y] , a[x][y] )) );
  81.                 }
  82.         }
  83.     }
  84. }
  85.  
  86. int main()
  87. {
  88.     F>>n>>m;
  89.     for (int i=2;i<=n+1;++i)
  90.         for (int j=2;j<=m+1;++j)
  91.             F>>a[i][j];
  92.     n += 2;
  93.     m += 2;
  94.  
  95.     for (int i=1;i<=n;++i)
  96.         for (int j=1;j<=m;++j)
  97.             D[i][j] = infi;
  98.  
  99.     Bellman(1,1);
  100.     for (int i=2;i<=n-1;++i)
  101.         for (int j=2;j<=m-1;++j)
  102.             volume += D[i][j] - a[i][j];
  103.  
  104.     G<<volume<<'\n';
  105.  
  106.     F.close();
  107.     G.close();
  108.     return 0;
  109. }
Success #stdin #stdout 0s 7940KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/po62Al
language:
C++ (gcc 8.3)
created:
10 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!