### Brief description:

在一個 N*M 的矩陣中尋找一個 A*B 的子矩陣，在這個 A*B 階的矩陣中再尋找一個 C*D 的子矩陣，

使得這兩個矩陣的差最大，另、C*D 子矩陣不可以觸碰 A*B 矩陣的邊界。

( .. N ≤ 1000 … ）

### Analysis:

枚舉一階子矩陣，對二階子矩陣和每列，分別維護單調隊列，時間複雜度 O(NM)。

const int N = 1001; struct MonoList{ int a[N], b[N]; int op, cz, nn; inline int size(){ return op - cz + 1; } inline int front(){ return a[cz]; } void init(){ a[0] = 0, op = -1, cz = 0; } void init(int l){ a[0] = 0, op = -1, cz = 0, nn = l; } void push_without_pop(int val, int label){ while (op >= cz && val <= a[op]){ --op; } a[++op] = val, b[op] = label; } void push(int val, int label){ push_without_pop(val, label); if (b[cz] + nn == b[op]) ++cz; } } Sub, Col[N]; int _T[101], s[N][N], ans; int n0, m0, n1, m1, n2, m2; inline int s1(int x, int y){ return s[x][y] - s[x-n1][y] - s[x][y-m1] + s[x-n1][y-m1]; } inline int s2(int x, int y){ return s[x][y] - s[x-n2][y] - s[x][y-m2] + s[x-n2][y-m2]; } int main(){ REP_1(i, 100) _T[i] = (i * 71 + 17) % 100 + 1; Rush{ RD(n0, m0, n1, m1, n2, m2); REP_1(i, n0) { int t; RD(t), s[i][1] = s[i-1][1] + t; FOR_1(j, 2, m0){ t = _T[t]; s[i][j] = s[i][j-1] + s[i-1][j] - s[i-1][j-1] + t; } } ans = 0; FOR(j, m2+1, m0) Col[j].init(n1 - n2 - 1); Sub.init(m1 - m2 - 1); FOR(i, n2+1, n1-1) FOR(j, m2+1, m0) Col[j].push_without_pop(s2(i, j), i); FOR_1(i, n1, n0){ FOR(j, m2+1, m0) Col[j].push(s2(i-1, j), i-1); Sub.init(); FOR(j, m2+1, m1) Sub.push_without_pop(Col[j].front(), j); FOR(j, m1, m0) { checkMax(ans, s1(i, j) - Sub.front()); Sub.push(Col[j].front(), j); } checkMax(ans, s1(i, m0) - Sub.front()); } OT(ans); } }