mickypinata

TOI9: Fence

Aug 1st, 2021
788
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int N = 500;
  5.  
  6. int qsum[N + 1][N + 1];
  7.  
  8. int getSum(int x1, int y1, int x2, int y2){
  9.     return qsum[x2][y2] - qsum[x1 - 1][y2] - qsum[x2][y1 - 1] + qsum[x1 - 1][y1 - 1];
  10. }
  11.  
  12. int main(){
  13.  
  14.     int Q = 2;
  15.     while(Q--){
  16.         int row, col, nTree;
  17.         scanf("%d%d%d", &row, &col, &nTree);
  18.         for(int i = 1; i <= N; ++i){
  19.             for(int j = 1; j <= N; ++j){
  20.                 qsum[i][j] = 0;
  21.             }
  22.         }
  23.         for(int i = 1; i <= nTree; ++i){
  24.             int r, c;
  25.             scanf("%d%d", &r, &c);
  26.             ++qsum[++r][++c];
  27.         }
  28.         for(int i = 1; i <= row; ++i){
  29.             for(int j = 1; j <= col; ++j){
  30.                 qsum[i][j] += qsum[i - 1][j] + qsum[i][j - 1] - qsum[i - 1][j - 1];
  31.             }
  32.         }
  33.         int mx = 0;
  34.         for(int d = 1; d <= min(row, col); ++d){
  35.             for(int i = 1; i <= row - d + 1; ++i){
  36.                 bool esc = false;
  37.                 for(int j = 1; j <= col - d + 1; ++j){
  38.                     int ir = i + d - 1;
  39.                     int jr = j + d - 1;
  40.                     int ans = getSum(i, j, ir, jr) - ((d > 2) ? getSum(i + 1, j + 1, ir - 1, jr - 1) : 0);
  41.                     if(ans == 0){
  42.                         mx = max(mx, d);
  43.                         esc = true;
  44.                         break;
  45.                     }
  46.                 }
  47.                 if(esc){
  48.                     break;
  49.                 }
  50.             }
  51.         }
  52.         cout << mx << '\n';
  53.     }
  54.  
  55.     return 0;
  56. }
  57.  
RAW Paste Data