Description

GZOI队员们到X镇游玩。X镇是一个很特别的城镇，它有m+1条东西方向和n+1条南北方向的道路，划分成m*n个区域，这些区域标从北到南、从西到东的坐标标识为从坐标 (1,1) 到坐标(m,n)。 GZOI队员们预先对这m*n个区域打分V(i，j)(分数可正可负)。分数越高表示他们越想到那个地方，越低表示他们越不想去。为了方便游玩，队员们需要选定一个连续的区域集合作为活动范围。例如，如果他们选择了最西北的区域(m1，nl)和最东南(m2，n2)区域(m1<=m2，n1<=n2),那他们的活动范围是 {D(i，j)|m1<=i<=m2，n1<=j<=n2}，其游览总分则为这些活动范围的区域总分。 GZOI队员们希望他们活动范围内的区域的分值总和最大。你的任务是编写一个程序，求出他们的活动范围(m1，nl)，(m2，n2〉。 

 

Input

输入第一行为整数m(1<=m<=200)，n(1<=n<=200)，用空格隔开 下面为m行，每行有n列整数，其中第i行第j列的整数，代表V(i,j)，每个整数之间用空格隔开，每个整数的范围是 [-200000,200000]，输入数据保证这些整数中，至少存在一个正整数。

Output

输出只有一行，为最高的分值。

 

Sample Input

4 51 -2 3 -4 56 7 8 9 10-11 12 13 14 -1516 17 18 19 20

Sample Output

146

 

 

题解

• 先搞一个前缀和，sum[i][j]表示第i行前j个的和
• 那么先O(n^2)枚举一个l和一个r
• 然后再O(n)暴力从上面往下加
• 如果ans<0把ans=0

代码

1 #include 
     
       2 #include 
      
        3 using namespace std; 4 int n,m,a[210][210]; 5 long long sum[210][210],ans,mx; 6 int main() 7 { 8     scanf("%d%d",&n,&m); 9     for (int i=1;i<=n;i++)10         for (int j=1;j<=m;j++)11         {12             scanf("%d",&a[i][j]);13             sum[i][j]=sum[i][j-1]+a[i][j];14         }15     for (int i=1;i<=m;i++)16         for (int j=i;j<=m;j++)17         {18             ans=0;19             for (int k=1;k<=n;k++)20             {21                 ans=ans+sum[k][j]-sum[k][i-1];22                 mx=max(mx,ans);23                 ans=ans<0?0:ans;24             }25         }26     printf("%lld",mx);27     return 0;28 }