fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define pii pair<int,int>
  3. #define endl cout<<"\n";
  4. #define fi first
  5. #define int long long
  6. #define se second
  7. #define ios ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
  8. #define op freopen
  9. #define TXT "test"
  10. #define freo if(fopen(TXT".inp","r")){op(TXT".inp","r",stdin);op(TXT".out","w",stdout);}
  11.  
  12. using namespace std;
  13.  
  14. const int MAXN = 1005;
  15. int n, m, p, q;
  16. int a[MAXN][MAXN], minRow[MAXN][MAXN], minMat[MAXN][MAXN];
  17.  
  18. int32_t main() {
  19.     ios;
  20.     freo;
  21.     cin >> n >> m >> p >> q;
  22.     for (int i = 1; i <= n; i++) {
  23.         for (int j = 1; j <= m; j++) {
  24.             cin >> a[i][j];
  25.         }
  26.     }
  27.     for (int i = 1; i <= n; i++) {
  28.         deque<int> dq;
  29.         for (int j = 1; j <= m; j++) {
  30.             while (!dq.empty() && dq.front() < j - q + 1) dq.pop_front();
  31.             while (!dq.empty() && a[i][dq.back()] >= a[i][j]) dq.pop_back();
  32.             dq.push_back(j);
  33.             if (j >= q) {
  34.                 minRow[i][j - q + 1] = a[i][dq.front()];
  35.             }
  36.         }
  37.     }
  38.     for (int j = 1; j <= m - q + 1; j++) {
  39.         deque<int> dq;
  40.         for (int i = 1; i <= n; i++) {
  41.             while (!dq.empty() && dq.front() < i - p + 1) dq.pop_front();
  42.             while (!dq.empty() && minRow[dq.back()][j] >= minRow[i][j]) dq.pop_back();
  43.             dq.push_back(i);
  44.             if (i >= p) {
  45.                 minMat[i - p + 1][j] = minRow[dq.front()][j];
  46.             }
  47.         }
  48.     }
  49.     int MAX = LLONG_MIN;
  50.     for (int i = 1; i <= n - p + 1; i++) {
  51.         for (int j = 1; j <= m - q + 1; j++) {
  52.             MAX = max(MAX, minMat[i][j]);
  53.         }
  54.     }
  55.  
  56.     cout << MAX;
  57. }
  58.  
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/4DdIdH
language:
C++ (gcc 8.3)
created:
9 days 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!