Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- const int N = 304, oo = 1e9 + 7;
- int m, n, k, a[N][N];
- int minVal[N], maxVal[N], res;
- deque<int> Min, Max;
- void Push(int pos) {
- while (Min.size() && minVal[Min.back()] > minVal[pos]) Min.pop_back();
- while (Max.size() && maxVal[Max.back()] < maxVal[pos]) Max.pop_back();
- Min.push_back(pos); Max.push_back(pos);
- }
- void Pop(int pos) {
- while (Max.size() && Max.front() <= pos) Max.pop_front();
- while (Min.size() && Min.front() <= pos) Min.pop_front();
- }
- void solve(int hei) {
- Min.clear(); Max.clear();
- int l = 1;
- for (int r = 1; r <= n; ++r) {
- Push(r);
- while (l <= r && maxVal[Max.front()] - minVal[Min.front()] > k) { Pop(l); ++l; }
- res = max(res, (r - l + 1) * hei);
- }
- }
- void process() {
- for (int i = 1; i <= m; ++i) {
- for (int id = 1; id <= n; ++id) minVal[id] = oo, maxVal[id] = -oo;
- for (int j = i; j <= m; ++j) {
- for (int id = 1; id <= n; ++id) {
- minVal[id] = min(minVal[id], a[j][id]);
- maxVal[id] = max(maxVal[id], a[j][id]);
- }
- solve(j - i + 1);
- }
- }
- cout << res;
- }
- int main() {
- ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
- freopen("LAND.inp", "r", stdin);
- freopen("LAND.out", "w", stdout);
- cin >> m >> n >> k;
- for (int i = 1; i <= m; ++i) for (int j = 1; j <= n; ++j) cin >> a[i][j];
- process();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement