/VM 09 Bài 08 - Giá trị chiếc quạt mo

              #include <iostream>
        #include <queue>
        using namespace std;
        
        #define INF 1000000000
        #define MAX 3001
        
        int m, n, K;
        int h[MAX][MAX];
        int hT[MAX][MAX]; // ma tran chuyen vi
        int f[MAX][MAX];
        int a[MAX], b[MAX];
        
        /*
          Ý tưởng: 
          + duyệt tất cả các trường hợp thỏa mãn nhưng có sự tối ưu
          + Sử dụng monotonic queue
        */
        
        int findRes(int m, int n, int h[][MAX]) {
          for (int i = 1; i <= m; i++) {
        
            for (int j = 1; j <= n; j++) {
              a[j] = -INF;
              b[j] = INF;
            }
            for (int j = i; j <= m; j++) { // i -> j
              int left = 1; int ans = 0;
              deque<int> qMax, qMin;
        
              for (int k = 1; k <= n; k++) {
                a[k] = max(a[k], h[j][k]);
                b[k] = min(b[k], h[j][k]);
        
                while (qMax.size() && qMax.back() < a[k]) qMax.pop_back();
                while (qMin.size() && qMin.back() > b[k]) qMin.pop_back();
        
                qMax.push_back(a[k]); 
                qMin.push_back(b[k]);
                while (left <= k && qMax.front() - qMin.front() > K) {
                  if (qMax.front() == a[left]) qMax.pop_front();
                  if (qMin.front() == b[left]) qMin.pop_front();
                  left++;
                }
        
                ans = max(ans, (j - i + 1) * (k - left + 1));
              }
        
              f[i][j] = ans;
            }
          }
        
          int res = 0;
          for (int i = 1; i < m; i++) {
        
            int r1 = 0, r2 = 0;
        
            for (int j = 1; j <= i; j++) {
              for (int k = j; k <= i; k++) {
                r1 = max(r1, f[j][k]);
              }
            }
        
            for (int j = i + 1; j <= m; j++) {
              for (int k = j; k <= m; k++) {
                r2 = max(r2, f[j][k]);
              }
            }
        
            res = max(res, r1 + r2);
        
          }
        
          return res;
        
        }
        
        int main() {
          cin >> m >> n >> K;
        
          for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
              cin >> h[i][j];
              hT[j][i] = h[i][j];
            }
          }
        
          int ans = max(findRes(m, n, h), findRes(n, m, hT));
        
          cout << ans << endl;
        
          return 0;
        }