fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. using ll = long long;
  5. using ull = unsigned long long;
  6. using pii = pair<int, int>;
  7.  
  8. template<typename X, typename Y>
  9. bool chmax(X& a, Y b) { return (a < b) ? a = b, 1 : 0; }
  10. template<typename X, typename Y>
  11. bool chmin(X& a, Y b) { return (a > b) ? a = b, 1 : 0; }
  12.  
  13. const ll INF = 1e18;
  14. const int N = 1005;
  15.  
  16. int n, m, k, T, a[N][N];
  17. ll P[N][N];
  18.  
  19. inline ll get(int i, int j, int x) { return P[i][j] - P[i - x][j] - P[i][j - x] + P[i - x][j - x]; }
  20.  
  21. bool check(int x) {
  22.     for (int i = x; i <= n; i++)
  23.         for (int j = x; j <= m; j++)
  24.             if (get(i, j, x) <= T)
  25.                 return true;
  26.     return false;
  27. }
  28.  
  29. void solve() {
  30.     cin >> n >> m >> k >> T;
  31.     for (int i = 1; i <= n; i++)
  32.         for (int j = 1; j <= m; j++) {
  33.             cin >> a[i][j];
  34.             P[i][j] = P[i - 1][j] + P[i][j - 1] - P[i - 1][j - 1] + a[i][j];
  35.         }
  36.     if (k == 1) {
  37.         int low = 1, high = n, ans = 0;
  38.         while (low <= high) {
  39.             int mid = low + (high - low) / 2;
  40.             if (check(mid)) ans = mid, low = mid + 1;
  41.             else high = mid - 1;
  42.         }
  43.         cout << ans * ans << '\n';
  44.         return;
  45.     }
  46.     int X = min(n, m);
  47.     vector<vector<ll>> top(n + 5, vector<ll>(X + 5, INF)), bottom(n + 5, vector<ll>(X + 5, INF));
  48.     vector<vector<ll>> left(m + 5, vector<ll>(X + 5, INF)), right(m + 5, vector<ll>(X + 5, INF));
  49.     for (int x = 1; x <= X; x++) {
  50.         for (int i = x; i <= n; i++)
  51.             for (int j = x; j <= m; j++) {
  52.                 ll S = get(i, j, x);
  53.                 if (S > T) continue;
  54.                 chmin(top[i][x], S); chmin(bottom[i - x + 1][x], S);
  55.                 chmin(left[j][x], S); chmin(right[j - x + 1][x], S);
  56.             }
  57.         for (int i = 1; i <= n; i++) chmin(top[i][x], top[i - 1][x]);
  58.         for (int i = n; i >= 1; i--) chmin(bottom[i][x], bottom[i + 1][x]);
  59.         for (int j = 1; j <= m; j++) chmin(left[j][x], left[j - 1][x]);
  60.         for (int j = m; j >= 1; j--) chmin(right[j][x], right[j + 1][x]);
  61.     }
  62.     int ans = 0;
  63.     for (int i = 1; i < n; i++) {
  64.         int X1 = min(i, X), X2 = min(n - i, X);
  65.         for (int x1 = 1; x1 <= X1; x1++) {
  66.             if (top[i][x1] > T) continue;
  67.             for (int x2 = 1; x2 <= X2; x2++)
  68.                 if (top[i][x1] + bottom[i + 1][x2] <= T)
  69.                     ans = max(ans, x1 * x1 + x2 * x2);
  70.         }
  71.     }
  72.     for (int j = 1; j < m; j++) {
  73.         int X1 = min(j, X), X2 = min(m - j, X);
  74.         for (int x1 = 1; x1 <= X1; x1++) {
  75.             if (left[j][x1] > T) continue;
  76.             for (int x2 = 1; x2 <= X2; x2++)
  77.                 if (left[j][x1] + right[j + 1][x2] <= T)
  78.                     ans = max(ans, x1 * x1 + x2 * x2);
  79.         }
  80.     }
  81.     cout << ans << '\n';
  82. }
  83.  
  84. int main() {
  85.     ios_base::sync_with_stdio(false); cin.tie(NULL);
  86.  
  87.     #define TASK "LAND"
  88.     if (fopen(TASK".INP", "r")) {
  89.         freopen(TASK".INP", "r", stdin);
  90.         freopen(TASK".OUT", "w", stdout);
  91.     }
  92.  
  93.     int tests = 1; // cin >> tests;
  94.     while (tests--) solve();
  95.  
  96.     return 0;
  97. }
Success #stdin #stdout 0s 5740KB
comments (?)
stdin
copy 
4 5 1
30
2 2 2 2 2
2 1 1 1 2
2 1 1 1 2
2 2 2 2 2
stdout
copy 
16
https://ideone.com/FTg1ma
language:
C++14 (gcc 8.3)
created:
18 hours 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!