fork(1) download 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define boost ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
  6. #define F first
  7. #define S second
  8.  
  9.  
  10. typedef long long ll;
  11. ll R,C,K;
  12.  
  13. ll grid[3001][3001];
  14. ll dp[3001][3001];
  15.  
  16.  
  17. ll ans ;
  18.  
  19. int main(){
  20.   boost;
  21.  
  22.   ll tt,T,i,j,k;
  23.   cin >> T;
  24.   for(tt = 1 ; tt <= T ; tt++){
  25.     ans = 0;
  26.     cin >> R >> C >> K;
  27.     memset(grid,0,sizeof(grid));
  28.     for(i = 0 ; i <= 3000 ; i++){
  29.       for(j = 0 ; j <= 3000 ; j++)
  30.        dp[i][j] = 0;
  31.     }
  32.  
  33.     for(i = 0 ; i < K ; i++){
  34.       ll r,c;
  35.       cin >> r >> c;
  36.       grid[r][c] = 1;
  37.     }
  38.  
  39.     for(i = 0 ; i < C ; i++){
  40.       if(grid[0][i] == 0)
  41.         dp[0][i] = 1;
  42.       else 
  43.         dp[0][i] = 0;
  44.     }
  45.  
  46.     for(i = 1 ; i < R ; i++){
  47.       if(grid[i][0] == 0)
  48.         dp[i][0] = 1;
  49.       else 
  50.         dp[i][0] = 0;
  51.     }
  52.  
  53.     for(i = 1 ; i < R ; i++){
  54.       for(j = 1 ; j < C ; j++){
  55.         if(grid[i][j] == 0)
  56.           dp[i][j] = min(dp[i][j-1],min(dp[i-1][j],dp[i-1][j-1]))+1;
  57.         else 
  58.           dp[i][j] = 0;
  59.       }
  60.     }
  61.     for(i = 0 ; i < R ; i++){
  62.       for(j = 0 ; j < C ; j++)
  63.         ans += dp[i][j];
  64.     }
  65.  
  66.  
  67.     cout << "Case #" << tt <<": "<<ans << endl;
  68.   }
  69. }
Success #stdin #stdout 0.06s 144192KB
comments (?)
stdin 
2
3 3 1
2 1
4 11 12
0 1
0 3
0 4
0 10
1 0
1 9
2 0
2 4
2 9
2 10
3 4
3 10
stdout 
Case #1: 10
Case #2: 51
https://ideone.com/VxdZ16
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
secret

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!