Advertisement
YEZAELP

TOI9: fence

Jul 26th, 2021
877
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.36 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. const int N = 5e2 + 10;
  5. const int M = 5e2 + 10;
  6. int qs[N][M];
  7. int n, m;
  8.  
  9. void Setting();
  10.  
  11. int Sum(int si, int sj, int ei, int ej){
  12.     if(si > ei or sj > ej) return 0;
  13.     return qs[ei][ej] - qs[si-1][ej] - qs[ei][sj-1] + qs[si-1][sj-1];
  14. }
  15.  
  16. bool Check(int limit){
  17.     int sum = 4 * limit - 4;
  18.     for(int i=limit;i<=n;i++){
  19.         for(int j=limit;j<=m;j++){
  20.             int SumBig = Sum(i - limit + 1, j - limit + 1, i, j);
  21.             int SumSmall = Sum(i - limit + 2, j - limit + 2, i - 1, j - 1);
  22.             if(SumBig - SumSmall == sum) return true;
  23.         }
  24.     }
  25.     return false;
  26. }
  27.  
  28. int Solve(){
  29.     int nPoint;
  30.     scanf("%d", &nPoint);
  31.     for(int i=1;i<=nPoint;i++){
  32.         int pi, pj;
  33.         scanf("%d%d", &pi, &pj);
  34.         pi ++, pj ++;
  35.         qs[pi][pj] = 0;
  36.     }
  37.     for(int i=1;i<=n;i++){
  38.         for(int j=1;j<=m;j++){
  39.             qs[i][j] += qs[i-1][j] + qs[i][j-1] - qs[i-1][j-1];
  40.         }
  41.     }
  42.  
  43.     for(int i=min(n, m);i>=1;i--){
  44.         if(Check(i)) return i;
  45.     }
  46.     return 0;
  47. }
  48.  
  49. int main(){
  50.  
  51.     int TC = 2;
  52.     while(TC --){
  53.         scanf("%d%d", &n, &m);
  54.         Setting();
  55.         printf("%d\n", Solve());
  56.     }
  57.  
  58.     return 0;
  59. }
  60.  
  61. void Setting(){
  62.     for(int i=1;i<=n;i++){
  63.         for(int j=1;j<=m;j++){
  64.             qs[i][j] = 1;
  65.         }
  66.     }
  67. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement