fork download
copy 
  1. #pragma comment(linker, "/stack:20000000")
  2. #pragma GCC optimize("Ofast")
  3. #pragma GCC target("sse,sse2,sse3,sse3,sse4,popcnt,abm,mmx")
  4.  
  5. #include <bits/stdc++.h>
  6.  
  7. #define f first
  8. #define s second
  9.  
  10. #define pb push_back
  11. #define pp pop_back
  12. #define mp make_pair
  13.  
  14. #define sz(x) (int)x.size()
  15. #define sqr(x) ((x) * 1ll * (x))
  16. #define all(x) x.begin(), x.end()
  17.  
  18. #define rep(i, l, r) for (int i = l; i <= r; i++)
  19. #define per(i, l, r) for (int i = l; i >= r; i--)
  20.  
  21. #define dbg(x) cerr << (#x) << " --> " << (x) << nl;
  22. #define Kazakhstan ios_base :: sync_with_stdio(0), cin.tie(0), cout.tie(0);
  23.  
  24. #define nl '\n'
  25. #define ioi exit(0);
  26.  
  27. using namespace std;
  28.  
  29. #ifdef superset
  30.   #include <ext/pb_ds/assoc_container.hpp>
  31.   #include <ext/pb_ds/tree_policy.hpp>
  32.   #include <ext/pb_ds/detail/standard_policies.hpp>
  33.  
  34.   using namespace __gnu_pbds;
  35.   typedef tree < pair <int, int>, null_type, less < pair <int, int> >, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
  36. #endif
  37.  
  38. typedef long long ll;
  39. typedef long double ld;
  40. typedef unsigned long long ull;
  41.  
  42. const int N = 350 + 7, inf = 1e9 + 7, mod = 1e9 + 7;
  43. const ll linf = (ll)1e18 + 7;
  44. const int dx[] = {-1, 0, 1, 0, 1, -1, -1, 1}, dy[] = {0, 1, 0, -1, 1, -1, 1, -1};
  45.  
  46. int get_int() {
  47.   char x = getchar();
  48.   bool mns = 0;
  49.   while (!isdigit(x)) mns |= x == '-', x = getchar();
  50.   int res = 0;
  51.   while (isdigit(x)) res = res * 10 + x - '0', x = getchar();
  52.   if (mns) res = -res;
  53.   return res;
  54. }
  55. void add(int &x, int y) {
  56.   x += y;
  57.   if (x >= mod) x -= mod;
  58.   if (x < 0) x += mod;
  59. }
  60. int mult(int x, int y) {
  61.   return x * 1ll * y % mod;
  62. }
  63. int sum(int x, int y) {
  64.   add(x, y);
  65.   return x;
  66. }
  67.  
  68. int n, m, k;
  69. int a[N][N];
  70. ll s[N][N];
  71.  
  72. ll get(int x1, int y1, int x2, int y2) {
  73.   return s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1];
  74. }
  75. bool z;
  76. bool corr(int x1, int y1, int x2, int y2, int lvl) {
  77.   if (x1 == x2 && y1 == y2) {
  78.     return a[x1][y1] <= lvl;
  79.   }
  80.   rep(i, y1, y2)
  81.     if (a[x1][i] > lvl || a[x2][i] > lvl) return 0;
  82.   rep(i, x1, x2) {
  83.     if (a[i][y1] > lvl || a[i][y2] > lvl) return 0;
  84.   }
  85.   return corr(x1 + 1, y1 + 1, x2 - 1, y2 - 1, lvl + 1);
  86. }
  87. bool check(int x) {
  88.   ll need = 0;
  89.   int len = x * 2 - 1;
  90.   for (int i = len; i >= 1; i -= 2) {
  91.     need += sqr(i);
  92.   }
  93.   for (int i = 1; i <= n - len + 1; i++) {
  94.     for (int j = 1; j <= m - len + 1; j++) {
  95.       if (need - get(i, j, i + len - 1, j + len - 1) <= k && corr(i, j, i + len - 1, j + len - 1, 1)) {
  96.         return 1;
  97.       }
  98.     }
  99.   }
  100.   return 0;
  101. }
  102. void solve() {
  103.   n = get_int(), m = get_int(), k = get_int();
  104.   memset(s, 0, sizeof(s));
  105.   rep(i, 1, n) {
  106.     rep(j, 1, m) {
  107.       a[i][j] = get_int();
  108.       s[i][j] = s[i - 1][j] + s[i][j - 1] + a[i][j] - s[i - 1][j - 1];
  109.     }
  110.   }
  111.   int l = 1, r = min((n + 1) / 2, (m + 1) / 2), res = 0;
  112.   rep(i, l, r)
  113.     if (check(i)) res = i;
  114.   printf ("%d\n", res);
  115. }
  116. int main() {
  117.   #ifdef IOI2018
  118.     #define Toktama ""
  119.     freopen (Toktama".in", "r", stdin);
  120.     //freopen (Toktama".out", "w", stdout);
  121.   #endif
  122.   int T = 1;
  123.   T = get_int();
  124.   while (T--)
  125.     solve();
  126.   ioi
  127. }
Time limit exceeded #stdin #stdout 5s 16736KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/fCzslB
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
public

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!