# 某島

… : "…アッカリ～ン . .. . " .. .
June 2, 2011

## SPOJ 912. Submatrix of submatrix

### Brief description:

( .. N ≤ 1000 … ）

### Analysis:


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);
}
}