#P2219. [HAOI2007] 修筑绿化带

    ID: 1235 远端评测题 1000ms 125MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>单调队列平衡树队列各省省选2007河南

[HAOI2007] 修筑绿化带

题目描述

为了增添公园的景致,现在需要在公园中修筑一个花坛,同时在花坛四周修建一片绿化带,让花坛被绿化带围起来。

如果把公园看成一个 M×NM\times N 的矩形,那么花坛可以看成一个 C×DC\times D 的矩形,绿化带和花坛一起可以看成一个 A×BA\times B 的矩形。

如果将花园中的每一块土地的“肥沃度”定义为该块土地上每一个小块肥沃度之和,那么,绿化带的肥沃度为 A×BA\times B 块的肥沃度减去 C×DC\times D 块的肥沃度。

为了使得绿化带的生长得旺盛,我们希望绿化带的肥沃度最大。

输入格式

第一行有六个正整数 M,N,A,B,C,DM,N,A,B,C,D

接下来一个 M×NM\times N 的数字矩阵,其中矩阵的第 iijj 列元素为一个整数 xi,jx_{i,j},表示该花园的第 ii 行第 jj 列的土地 “肥沃度”。

输出格式

一个正整数,表示绿化带的最大肥沃程度。

4 5 4 4 2 2
20 19 18 17 16
15 14 13 12 11
10 9 8 7 6
5 4 3 2 1

132

提示

对于 30%30\% 的数据,1M,N501\leq M,N\leq 50

对于 100%100\% 的数据,1M,N10001\leq M,N\leq 10001AM1\leq A\leq M1BN1\leq B\leq N1CA21\leq C\leq A-21DB21\leq D\leq B-21xi,j1001\leq x_{i,j}\leq 100