Advertisement
Dang_Quan_10_Tin

MAXR

Sep 28th, 2022
867
0
Never
1
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.95 KB | None | 0 0
  1. #define task "MAXR"
  2. #include <iostream>
  3. #include <cstdio>
  4.  
  5. using namespace std;
  6.  
  7. using ll = long long;
  8. using ld = long double;
  9. template <class T>
  10. void readInt(T &x)
  11. {
  12.     x = 0;
  13.     register int c;
  14.     while ((c = getchar()) && (c > '9' || c < '0'))
  15.         ;
  16.     for (; c >= '0' && c <= '9'; c = getchar())
  17.         x = x * 10 + c - '0';
  18. }
  19.  
  20. constexpr int N = 5e3 + 5;
  21. int m, n;
  22. int a[N][N], f[N][N];
  23. int b[N * 2][N * 2];
  24.  
  25. void Read()
  26. {
  27.     // cin >> m >> n;
  28.     readInt(m), readInt(n);
  29.  
  30.     for (int i = 1; i <= m; ++i)
  31.         for (int j = 1; j <= n; ++j)
  32.             // cin >> a[i][j];
  33.             readInt(a[i][j]);
  34. }
  35.  
  36. int S(int k)
  37. {
  38.     // 1 3 5 ... 2k + 1 ... 5 3 1
  39.     return k * (2 * k) + 2 * k + 1;
  40. }
  41.  
  42. int Get(int x, int y, int z, int t)
  43. {
  44.     return b[z][t] - b[x - 1][t] - b[z][y - 1] + b[x - 1][y - 1];
  45. }
  46.  
  47. int Get(int i, int j, int k)
  48. {
  49.     int x = i + j - 1,
  50.         y = i + n - j;
  51.  
  52.     return Get(x - k, y - k, x + k, y + k);
  53. }
  54.  
  55. void Solve()
  56. {
  57.     for (int i = 1; i <= m; ++i)
  58.         for (int j = 1; j <= n; ++j)
  59.             b[i + j - 1][i + (n - j)] = a[i][j];
  60.  
  61.     for (int i = 1; i <= m + n - 1; ++i)
  62.         for (int j = 1; j <= m + n - 1; ++j)
  63.             b[i][j] += b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1];
  64.  
  65.     int ans(0);
  66.  
  67.     for (int i = 1; i <= m; ++i)
  68.         for (int j = 1; j <= n; ++j)
  69.         {
  70.             f[i][j] = min(f[i - 1][j] + 1, f[i][j - 1] + 1);
  71.             f[i][j] = min(f[i][j], min(i - 1, j - 1));
  72.             f[i][j] = min(f[i][j], min(m - i, n - j));
  73.  
  74.             while (f[i][j] && Get(i, j, f[i][j]) != S(f[i][j]))
  75.                 --f[i][j];
  76.  
  77.             ans = max(ans, f[i][j]);
  78.         }
  79.  
  80.     cout << ans;
  81. }
  82.  
  83. int32_t main()
  84. {
  85.     ios_base::sync_with_stdio(0);
  86.     cin.tie(0);
  87.     cout.tie(0);
  88.  
  89.     if (fopen(task ".INP", "r"))
  90.     {
  91.         freopen(task ".INP", "r", stdin);
  92.         freopen(task ".OUT", "w", stdout);
  93.     }
  94.  
  95.     Read();
  96.     Solve();
  97. }
Advertisement
Comments
Add Comment
Please, Sign In to add comment
Advertisement