记录编号	576983	评测结果	AAAAAAAAAA
题目名称	[IOI 1999]矩形地块（A Strip of Land）	最终得分	100
用户昵称	lihaoze	是否通过	通过
代码语言	C++	运行时间	1.583 s
提交时间	2022-10-19 20:33:00	内存使用	6.90 MiB

#include <bits/stdc++.h>

using PII = std::pair<int, int>;

const int N = 710, INF = 0x3f3f3f3f;
int n, m, c, ans;
int a[N][N], max[N], min[N];

struct deque {
    std::deque<PII> s;
    void pop(int x) {
        if (s.size() && s.front().first == x)
            s.pop_front();
    }
    int front() {
        return s.front().second;
    }
    void push(int x, int v) {
        while (s.size() && s.back().second >= v)
            s.pop_back();
        s.push_back({ x, v });
    }
};

int maxLen() {
    int l = 1, r = 1, res = 0;
    deque nmx, nmn;
    while (r <= n) {
        nmn.push(r, min[r]), nmx.push(r, -max[r]);
        while (l <= r && -nmx.front() - nmn.front() > c)
            nmn.pop(l), nmx.pop(l), ++ l;
        res = std::max(res, r - l + 1), ++ r;
    }
    return res;
}

int main() {
    freopen("land.in", "r", stdin); 
    freopen("land.out", "w", stdout);
    std::cin >> m >> n >> c;
    for (int i = 1; i <= n; ++ i) 
        for (int j = 1; j <= m; ++ j)
            std::cin >> a[i][j];
    for (int i = 1; i <= m; ++ i) {
        for (int j = 1; j <= n; ++ j) 
            max[j] = -INF, min[j] = INF;
        int t = m;
        for (int j = i; j < i + 100 && j <= m; ++ j) {
            for (int k = 1; k <= n; ++ k) {
                max[k] = std::max(max[k], a[k][j]),
                min[k] = std::min(min[k], a[k][j]);
            }
            if (t * (j - i + 1) <= ans) continue;
            t = maxLen(), ans = std::max(ans, t * (j - i + 1));
        }
    }
    std::cout << ans << '\n';
    return 0;
}