Ankit_132

E

Jul 22nd, 2023
221
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.04 KB | None | 0 0
  1.  
  2. #include <bits/stdc++.h>
  3.  
  4. using namespace std;
  5.  
  6. #define ll     long long
  7. #define _test   int _TEST; cin>>_TEST; while(_TEST--)
  8. #define ff     first
  9. #define ss     second
  10. #define pb     push_back
  11.  
  12. int main()
  13. {
  14.     int n, m;
  15.     cin>>n>>m;
  16.  
  17.     vector<vector<int>> a(n, vector<int> (m));
  18.  
  19.     int N;
  20.     cin>>N;
  21.  
  22.     for(int i=0; i<N; i++)
  23.     {
  24.         int x, y;
  25.         cin>>x>>y;
  26.  
  27.         x--, y--;
  28.  
  29.         a[x][y] = 1;
  30.     }
  31.  
  32.     vector<vector<ll int>> vals(n, vector<ll int> (m));
  33.     ll int ans = 0;
  34.  
  35.     for(int i=0; i<n; i++)
  36.     {
  37.         for(int j=0; j<m; j++)
  38.         {
  39.             if(i==0 || j==0)
  40.             {
  41.                 if(a[i][j] == 1)    vals[i][j] = 0;
  42.                 else                vals[i][j] = 1;
  43.             }
  44.             else
  45.             {
  46.                 if(a[i][j] == 1)    vals[i][j] = 0;
  47.                 else                vals[i][j] = min({vals[i-1][j], vals[i][j-1], vals[i-1][j-1]}) + 1;
  48.             }
  49.  
  50.             ans += vals[i][j];
  51.         }
  52.     }
  53.  
  54.     cout<<ans<<"\n";
  55. }
  56.  
Advertisement
Add Comment
Please, Sign In to add comment