记录编号	116613	评测结果	AAAAAAAAAA
题目名称	24.[HAOI 2007]修筑绿化带	最终得分	100
用户昵称	rpCardinal	是否通过	通过
代码语言	C++	运行时间	0.458 s
提交时间	2014-08-26 13:03:59	内存使用	15.87 MiB

#include <cstdio>
#include <algorithm>
#include <deque>
using namespace std;

int N,M,A,B,C,D,i,j,a[1010][1010],s[1010][1010],s1[1010][1010],s2[1010][1010],ans;
char ch;
deque <int> q;

void read(int &x)
{
    ch=getchar(); x=0;
    while (ch<=32) ch=getchar();
    while (ch>32)
    {
        x=x*10+ch-48;
        ch=getchar();
    }
}

int main()
{
    freopen("parterre.in","r",stdin);
    freopen("parterre.out","w",stdout);
    read(M); read(N); read(A); read(B); read(C); read(D);
    for (i=1;i<=M;++i)
        for (j=1;j<=N;++j)
        {
            read(a[i][j]);
            s[i][j]=a[i][j]+s[i-1][j]+s[i][j-1]-s[i-1][j-1];
        }
    for (i=C;i<=M;++i)
        for (j=D;j<=N;++j)
        {
            s2[i][j]=s[i][j]-s[i-C][j]-s[i][j-D]+s[i-C][j-D];
            if (i>=A&&j>=B)
                s1[i][j]=s[i][j]-s[i-A][j]-s[i][j-B]+s[i-A][j-B];
        }
    /*for (i=1;i<=M;++i)
    {
        for (j=1;j<=N;++j)
            printf("%d ",s2[i][j]);
        putchar('\n');
    }*/
    for (i=C;i<=M;++i)
    {
        while (!q.empty()) q.pop_back();
        for (j=D;j<=N;++j)
        {
            while (!q.empty()&&s2[i][q.back()]>=s2[i][j]) q.pop_back();
            q.push_back(j);
            if (q.front()<=j-B+D+1) q.pop_front();
            if (j>=B-1) s[i][j]=s2[i][q.front()];
        }
    }
    /*for (i=C;i<=M;++i)
    {
        for (j=B-1;j<=N;++j)
            printf("%d ",s[i][j]);
        putchar('\n');
    }*/
    for (j=B;j<=N;++j)
    {
        while (!q.empty()) q.pop_back();
        for (i=C;i<=M;++i)
        {
            while (!q.empty()&&s[q.back()][j-1]>=s[i-1][j-1]) q.pop_back();
            q.push_back(i-1);
            if (q.front()<=i-A+C) q.pop_front();
            if (i>=A) ans=max(ans,s1[i][j]-s[q.front()][j-1]);
        }
    }
    printf("%d\n",ans);
    fclose(stdin); fclose(stdout);
    return 0;
}