Advertisement
Guest User

Untitled

a guest
Oct 17th, 2018
78
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.49 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int N = 304, oo = 1e9 + 7;
  5. int m, n, k, a[N][N];
  6.  
  7. int minVal[N], maxVal[N], res;
  8. deque<int> Min, Max;
  9.  
  10. void Push(int pos) {
  11.     while (Min.size() && minVal[Min.back()] > minVal[pos]) Min.pop_back();
  12.     while (Max.size() && maxVal[Max.back()] < maxVal[pos]) Max.pop_back();
  13.     Min.push_back(pos); Max.push_back(pos);
  14. }
  15.  
  16. void Pop(int pos) {
  17.     while (Max.size() && Max.front() <= pos) Max.pop_front();
  18.     while (Min.size() && Min.front() <= pos) Min.pop_front();
  19. }
  20.  
  21. void solve(int hei) {
  22.     Min.clear(); Max.clear();
  23.  
  24.     int l = 1;
  25.     for (int r = 1; r <= n; ++r) {
  26.         Push(r);
  27.         while (l <= r && maxVal[Max.front()] - minVal[Min.front()] > k) { Pop(l); ++l; }
  28.  
  29.         res = max(res, (r - l + 1) * hei);
  30.     }
  31. }
  32.  
  33. void process() {
  34.     for (int i = 1; i <= m; ++i) {
  35.         for (int id = 1; id <= n; ++id) minVal[id] = oo, maxVal[id] = -oo;
  36.  
  37.         for (int j = i; j <= m; ++j) {
  38.             for (int id = 1; id <= n; ++id) {
  39.                 minVal[id] = min(minVal[id], a[j][id]);
  40.                 maxVal[id] = max(maxVal[id], a[j][id]);
  41.             }
  42.  
  43.             solve(j - i + 1);
  44.         }
  45.     }
  46.  
  47.     cout << res;
  48. }
  49.  
  50. int main() {
  51.     ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  52.     freopen("LAND.inp", "r", stdin);
  53.     freopen("LAND.out", "w", stdout);
  54.  
  55.     cin >> m >> n >> k;
  56.     for (int i = 1; i <= m; ++i) for (int j = 1; j <= n; ++j) cin >> a[i][j];
  57.  
  58.     process();
  59.  
  60.     return 0;
  61. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement