| 记录编号 |
95836 |
评测结果 |
AAAAAAAAAA |
| 题目名称 |
[HAOI 2007]修筑绿化带 |
最终得分 |
100 |
| 用户昵称 |
 Mongo |
是否通过 |
通过 |
| 代码语言 |
C++ |
运行时间 |
0.838 s |
| 提交时间 |
2014-04-09 15:43:31 |
内存使用 |
27.05 MiB |
显示代码纯文本
//#define lgg
#include <cstdio>
#include <algorithm>
#include <climits>
using namespace std;
int N, M, A, B, C, D, t[1001][1001];
int AB[2][1001][1001], CD[4][1001][1001], ans;
void read(), inti(), calc_AB(), calc_CD(), work(), find_x(), find_y(), minus();
int main()
{
freopen("parterre.in", "r", stdin); freopen("parterre.out", "w", stdout);
read();
inti();
work();
printf("%d\n", ans);
return 0;
}
inline void read()
{
scanf("%d%d%d%d%d%d", &M, &N, &A, &B, &C, &D);
for(int i(1); i<=M; ++i)
for(int j(1); j<=N; ++j)
scanf("%d", &t[i][j]);
return;
}
inline void inti()
{
calc_AB();
calc_CD();
}
inline void calc_AB()
{
int sum;
for(int i(1); i<=M; ++i)
{
sum=0;
for(int j(1); j<=B; ++j)
sum+=t[i][j];
AB[1][i][1]=sum;
}
for(int i(1); i<=M; ++i)
for(int j(2); j<=N-B+1; ++j)
AB[1][i][j]=AB[1][i][j-1]+t[i][j+B-1]-t[i][j-1];
for(int i(1); i<=N-B+1; ++i)
{
sum=0;
for(int j(1); j<=A; ++j)
sum+=AB[1][j][i];
AB[0][1][i]=sum;
}
for(int i(1); i<=N-B+1; ++i)
for(int j(2); j<=M-A+1; ++j)
AB[0][j][i]=AB[0][j-1][i]+AB[1][j+A-1][i]-AB[1][j-1][i];
#ifdef lgg
for(int i(1); i<=M-A+1; ++i)
{
for(int j(1); j<=N-B+1; ++j)
{
sum=0;
for(int m(0); m<A; ++m)
for(int n(0); n<B; ++n)
sum+=t[i+m][j+n];
if(sum!=AB[0][i][j])
{
printf("error: %d, %d\n", i, j);
abort();
}
printf("%d ", AB[0][i][j]);
}
putchar('\n');
}
putchar('\n');
#endif
}
inline void calc_CD()
{
int sum;
for(int i(1); i<=M; ++i)
{
sum=0;
for(int j(1); j<=D; ++j)
sum+=t[i][j];
CD[1][i][1]=sum;
}
for(int i(1); i<=M; ++i)
for(int j(2); j<=N-D+1; ++j)
CD[1][i][j]=CD[1][i][j-1]+t[i][j+D-1]-t[i][j-1];
for(int i(1); i<=N-D+1; ++i)
{
sum=0;
for(int j(1); j<=C; ++j)
sum+=CD[1][j][i];
CD[0][1][i]=sum;
}
for(int i(1); i<=N-D+1; ++i)
for(int j(2); j<=M-C+1; ++j)
CD[0][j][i]=CD[0][j-1][i]+CD[1][j+C-1][i]-CD[1][j-1][i];
#ifdef lgg
for(int i(1); i<=M-C+1; ++i)
{
for(int j(1); j<=N-D+1; ++j)
{
sum=0;
for(int m(0); m<C; ++m)
for(int n(0); n<D; ++n)
sum+=t[i+m][j+n];
if(sum!=CD[0][i][j])
{
printf("error: %d, %d\n", i, j);
abort();
}
printf("%d ", CD[0][i][j]);
}
putchar('\n');
}
putchar('\n');
#endif
}
inline void work()
{
find_x();
find_y();
minus();
return;
}
struct nd
{
int id, val;
nd():id(0), val(0){}
nd(int a, int b):id(a), val(b){}
};
bool operator<=(const nd& a, const nd& b)
{
return a.val<=b.val;
}
struct dandiao
{
nd q[1001];
int beg, end, maxsz; //end超出范围，maxsz制定单调队列大小
inline void clear()
{
beg=end=0;
return;
}
inline void prepush(nd a)
{
int in(end-1);
while(in>=beg && a<=q[in])
--in;
q[++in]=a;
end=in+1;
return;
}
inline void push(nd a)
{
int in(end-1);
while(in>=beg && a<=q[in])
--in;
q[++in]=a;
end=in+1;
while(a.id-q[beg].id>=maxsz)
++beg;
return;
}
inline int front()
{
return q[beg].val;
}
}q;
inline void find_x()
{
q.maxsz=B-D-1;
for(int i(1); i<=M-C+1; ++i)
{
q.clear();
for(int j(1); j<q.maxsz; ++j)
q.prepush(nd(j, CD[0][i][j]));
for(int j(q.maxsz); j<=N-D+1; ++j)
{
q.push(nd(j, CD[0][i][j]));
CD[2][i][j-q.maxsz+1]=q.front();
}
}
return;
}
inline void find_y()
{
q.maxsz=A-C-1;
for(int i(1); i<=N-B+3; ++i)
{
q.clear();
for(int j(1); j<q.maxsz; ++j)
q.prepush(nd(j, CD[2][j][i]));
for(int j(q.maxsz); j<=M-C+1; ++j)
{
q.push(nd(j, CD[2][j][i]));
CD[3][j-q.maxsz+1][i]=q.front();
}
}
/*for(int i(1); i<=N-B+3; ++i)
for(int j(1); j<=M-C+1; ++j)
{
int mm(INT_MAX);
for(int m(0); m<q.maxsz; ++m)
mm=min(mm, CD[2][j+m][i]);
if(mm!=CD[3][j][i])
{
printf("");
}
}*/
return;
}
inline void minus()
{
#ifdef lgg
for(int i(1); i<=M-A+3; ++i)
{
for(int j(1); j<=N-B+3; ++j)
{
int s(INT_MAX);
for(int m(0); m<A-C-1; ++m)
for(int n(0); n<B-D-1; ++n)
s=min(s, CD[0][i+m][j+n]);
AB[2][i][j]=s;
/*if(s!=CD[2][i][j])
{
printf("error: %d, %d\n", i, j);
abort();
}*/
printf("%d,%d ", CD[3][i][j], AB[2][i][j]);
}
putchar('\n');
}
putchar('\n');
#endif
for(int i(1); i<=M-A+1; ++i)
for(int j(1); j<=N-B+1; ++j)
ans=max(ans, AB[0][i][j]-CD[3][i+1][j+1]);
return;
}