背景 Background
一片幻影闪过，眼花缭乱，什么都看不清……
终于，一切平静了下来。一袭白衣，礼帽，斗篷，手套，皮鞋，闪着光的镜片下出现一张英俊的脸庞（啊！！OIBH组织众女生花痴ing）……
怪盗基德浅浅一笑，想要困住我，还差点本事呢！（啊！！能杀人的笑……OIBH组织众女生继续花痴ing）那么，女士们，先生们，就让我，举世闻名的魔术师，为各位献上一场独一无二的魔术秀吧！
掌声雷动……掌声雷动……撒花……撒花……
第1009号小兵屁颠屁颠从门口跑过来，刚想开口喊：“抓基德啊！！”却不禁被眼前华丽的魔术吸引了……
描述 Description
在越过了第一道关卡之后，KID暂时摆脱了OIBH组织的追兵。基德为了不被打扰，决定送给OIBH组织一份大礼：那就是扑克阵法。基德的扑克阵法是扑克牌组成的N*N的大方阵，要解开这个阵法的要诀就是，拿走两个互不重叠的K*K的方阵中的扑克牌，使得这2*k^2张扑克牌的总分最大，从而使整个阵法失去主要能量而土崩瓦解。但是，基德自己在偷完回去的路上也会碰到这个阵法——为了不至于自己把自己困住——基德需要你帮助他编程解决这个阵法。
输入格式 Input Format
第1行两个数n，k。
第2行到第n+1行，每行n个非负整数，表示整个扑克阵法每张牌的分值。
输出格式 Output Format
一个数，表示最大能拿走的总分。
样例输入 Sample Input
4 2
1 1 1 1
8 8 1 1
8 8 9 9
1 1 9 9
样例输出 Sample Output
68
注释 Hint
对于20%的数据,1<=k<=n<=50
对于100%的数据,1<=k<=n<=1000
保证答案不超过2^31-1。
分析：
显然，一定能在大方阵里找到一条直线（横的或者竖的），把大方阵分裂成两部分，从而使得两个子方阵分别位于两个部分里（利用反证法，若找不到则两个子方阵一定有重叠部分）。
因此预处理两个数组maxr,maxl，其中maxr[i]表示以i为左边界的部分的最大子方阵权值。maxl则反之。最后只要统计maxr[i]+maxl[i-1]的最大值即可。注意那条线有可能是水平的，因此还要把输入数据旋转90度再做一遍。通过预处理，这个算法可以降低复杂度，极限数据0.40s出解。
【参考程序】：
#include<cstring>
#include<cstdio>
#include<iostream>
using namespace std;
typedef int array[1010][1010];
array a,b,sum;
int maxr[1010],maxl[1010];
int n,k;
void solve()
{
memset(sum,0,sizeof(sum));
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
sum[i][j]+=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+a[i][j];
memset(maxl,0,sizeof(maxl));
for (int i=k;i<=n-k+1;i++)
{
maxl[i]=maxl[i-1];
for (int j=k;j<=n;j++)
if (maxl[i]<sum[i][j]-sum[i-k][j]-sum[i][j-k]+sum[i-k][j-k])
maxl[i]=sum[i][j]-sum[i-k][j]-sum[i][j-k]+sum[i-k][j-k];
}
memset(maxr,0,sizeof(maxr));
for (int i=n-k+1;i>=k+1;i--)
{
maxr[i]=maxr[i+1];
for (int j=1;j<=n-k+1;j++)
if (maxr[i]<sum[i+k-1][j+k-1]-sum[i-1][j+k-1]-sum[i+k-1][j-1]+sum[i-1][j-1])
maxr[i]=sum[i+k-1][j+k-1]-sum[i-1][j+k-1]-sum[i+k-1][j-1]+sum[i-1][j-1];
}
}
void turn()
{
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
b[i][j]=a[j][n-i+1];
memcpy(a,b,sizeof(a));
}
int main()
{
scanf("%d%d",&n,&k);
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
scanf("%d",&a[i][j]);
solve();
int ans=0;
for (int i=k;i<=n-k;i++)
if (ans<maxl[i]+maxr[i+1])
ans=maxl[i]+maxr[i+1];
turn();
solve();
for (int i=k;i<=n-k;i++)
if (ans<maxl[i]+maxr[i+1])
ans=maxl[i]+maxr[i+1];
printf("%d\n",ans);
return 0;
}