2017.7.21夏令营清北学堂解题报告,2017.7.21夏令营

预测分数:

60+30+0=90=划水

实在分数:

90+30+20=140=rank5=异极鼠标

一句话总括:后天该买彩票!

 

T1:

澳门新葡萄京官网注册 1难题陈述早前有一个?行?列的网格。 今后有?种颜色,第?种颜色能够涂??格,保证 Σ︀ ??
= ? * ?。
需求你对那些网格图举行着色,你一定要根据从上到下,每大器晚成行内从左到右
的顺序实行着色,况兼在用完意气风发种颜色前您无法换颜色(当然颜色的施用各样是随机的)。
各类相邻的等同色块能够收获1分,问在给定的平整下张开着色所能得到的
最高分是有一点点。 多组数据。 输入输出格式 输入格式:
从文件diyiti.in中读入数据。 第生龙活虎行叁个卡尺头?表示数据组数。
对于每组数据,第后生可畏行三个整数?, ?, ?表示网格的大小和颜料的数码。
之后大器晚成行?个数,第?个数表示第?种颜色能够涂的格数。 输出格式:
将答案输出到diyiti.out。 对于每组数据一个数???,表示能获得的万丈分。
输入输出样例 输入样例#1: 2 3 3 4 1 2 2 4 4 2 4 1 2 2 3 输出样例#1: 5
4 认证 【样例解释】 第风流倜傥组数据 1 2 2 3 3 4 4 4 4 第二组数据 1 4 4 4 2 2
3 3 对于二成的数据,1 ≤ ?, ? ≤ 10, 1 ≤ ? ≤ 2 对于百分之三十的数目,1 ≤ ?, ? ≤
1000, 1 ≤ ? ≤ 3 对于100%的数码,1 ≤ ?, ? ≤ 100000, 1 ≤ ? ≤ 4, ?? ≥ 1, ?
≤ 10 3 T1

认为这题好鬼畜,平昔不曾见过那种类型的题,大器晚成开首噼里啪啦的敲了90+行的武力,

意料之中只好过十分之四的数目,不能,只可以留着对拍了。。。。

新兴开采了八个公式:

当p%m==0的时候的方案数是:((m-1卡塔尔(قطر‎+(p/m-1State of Qatar*(m*2-1));

接下来特判一下种种情况搞风华正茂搞就好了,

预测能过60%的数量,

但是最终仍然得了90分,,

何况此外的百般不精通怎么丢的,,,,=.=

暴力:

 

澳门新葡萄京官网注册 2 1
#include<iostream> 2 #include<cstdio> 3
#include<cstring> 4 #include<algorithm> 5
#include<queue> 6 using namespace std; 7 const int MAXN=100001; 8
const int maxn=0x7ffff; 9 void read(int &n) 10 { 11 char c=’+’;int
x=0;bool flag=0; 12
while(c<‘0’||c>’9′){c=getchar();if(c==’-‘)flag=1;} 13
while(c>=’0’&&c<=’9’) 14
x=(x<<1)+(x<<3)+c-48,c=getchar(); 15 flag==1?n=-x:n=x; 16 }
17 int T; 18 int n,m,colornum; 19 int color[MAXN]; 20 int
map[MAXN][6]; 21 int ans=0; 22 int xx[5]={-1,+1,0,0}; 23 int
yy[5]={0,0,-1,+1}; 24 int vis[MAXN]; 25 void dfs(int used,int bh,int
coloruse,int x,int yState of Qatar 26 // 使用了的水彩 当前点的号码 当前已利用 27 { 28
if(used==colornum&&coloruse==color[bh]) 29 { 30 int now=0; 31 for(int
i=1;i<=n;i++) 32 for(int j=1;j<=m;j++) 33 for(int k=0;k<4;k++)
34 { 35 int wx=i+xx[k]; 36 int wy=j+yy[k]; 37
if(wx>=1&&wx<=n&wy>=1&&wy<=m) 38
if(map[i][j]==map[wx][wy]) 39 now++; 40 } 41 42
ans=max(ans,now/2); 43 return ; 44 } 45 int wx,wy; 46 if(y==m) {
wy=1;wx=x+1;} 47 else { wy=y+1; wx=x; } 48 if(coloruse==color[bh]) 49
{ 50 vis[bh]=1; 51 for(int i=1;i<=colornum;i++) 52 { 53
if(!vis[i]) 54 { 55 // vis[i]=1; 56 map[wx][wy]=i; 57
dfs(used+1,i,1,wx,wy); 58 map[wx][wy]=0; 59 // vis[i]=0; 60 } 61 }
62 vis[bh]=0; 63 } 64 else 65 { 66 map[wx][wy]=bh; 67
dfs(used,bh,coloruse+1,wx,wy); 68 map[wx][wy]=0; 69 } 70 71 } 72 int
main() 73 { 74 // freopen(“diyiti.in”,”r”,stdin); 75 //
freopen(“diyiti.out”,”w”,stdout); 76 // 77 read(T); 78 while(T–) 79 {
80 memset(vis,0,sizeof(vis)); 81 memset(map,0,sizeof(map)); 82
memset(color,0,sizeof(color)); 83 ans=0; 84
read(n);read(m);read(colornum); 85 if(n>=0) 86 { 87 for(int
i=1;i<=colornum;i++) 88 read(color[i]); 89 for(int
i=1;i<=colornum;i++) 90 { 91 // vis[color[i]]=1; 92
map[1][1]=i; 93 dfs(1,i,1,1,1); 94 map[1][1]=0; 95
//vis[color[i]]=0; 96 } 97 printf(“%dn”,ans); 98 } 99 else 100 {
101 int p; 102 if(colornum==n*m) 103 { 104 for(int
i=1;i<=colornum;i++) 105 read(p); 106 printf(“0n”卡塔尔国; 107 continue;
108 } 109 if(m==1State of Qatar 110 { 111 for(int i=1;i<=colornum;i++State of Qatar 112 { 113
read(p卡塔尔; 114 ans+=p-1;//上下多个相邻 115 } 116 } 117 else if(m==2State of Qatar 118 {
119 for(int i=1;i<=colornum;i++State of Qatar 120 { 121 read(p卡塔尔; 122 if(p==1卡塔尔(قطر‎ 123
continue;// 没有相邻 124 else 125 ans+=((m-1卡塔尔国+(p/m-1State of Qatar*(m*2-1卡塔尔国卡塔尔(قطر‎+p%m;
126 } 127 } 128 else if(m==3卡塔尔国 129 { 130 for(int i=1;i<=colornum;i++卡塔尔(قطر‎131 { 132 read(p); 133 if(p==1卡塔尔国 134 continue; 135 if(p<mState of Qatar 136 if(p%2卡塔尔国137 ans+=p-1;// 左右相邻 138 else 139 ans+=p-2; 140 else 141 { 142
ans+=((m-1卡塔尔国+(p/m-1卡塔尔(قطر‎*(m*2-1)); 143 int remain=p%3; 144 if(remain!=0)
145 ans+=(remain*2-1); 146 } 147 } 148 } 149 else if(m==4) 150 { 151
for(int i=1;i<=colornum;i++) 152 { 153 read(p); 154 if(p==1) 155
continue; 156 if(p<m) 157 ans+=p-1; 158 else 159 { 160
ans+=((m-1)+(p/m-1)*(m*2-1)); 161 int remain=p%4; 162 if(remain!=0)
163 ans+=(remain*2-1); 164 } 165 } 166 } 167 printf(“%dn”,ans); 168 }
169 } 170 return 0; 171 } T1暴力

 

澳门新葡萄京官网注册 3 1
#include<bits/stdc++.h> 2 using namespace std; 3 int
T,n,m,S,a[100010],p[5],ans; 4 int main(){ 5
freopen(“diyiti3.in”,”r”,stdin); 6 freopen(“diyiti3.out”,”w”,stdout); 7
scanf(“%d”,&T); 8 while(T–){ 9 memset(p,0,sizeof(p)); 10 ans=0; 11
scanf(“%d%d%d”,&n,&m,&S); 12 for(int i=1;i<=S;i++){ 13
scanf(“%d”,&a[i]); 14 p[a[i]%m]++; 15
if(a[i]>=m)ans+=(a[i]/m*(2*m-1)-m+a[i]%m+max(0,a[i]%m-1));
16 else ans+=a[i]-1; 17 } 18 if(m==3){ 19
if(p[2]>p[1])ans-=(p[2]-p[1])/3; 20 }else if(m==4){ 21
if(p[3]>p[1])ans-=(p[3]-p[1])/2; 22 } 23 printf(“%dn”,ans);
24 } 25 } T1正解

 

T2:

 

澳门新葡萄京官网注册 4标题陈说在纸上有二个长为?的数列,第?项值为??。
未来小A想要在此些数以内增多加号或乘号。问对此不相同的2?−1种方案,
全部答案的和是微微? 由于数量范围比较大,所以输出对1000000007取模的结果。
输入输出格式 输入格式: 从文件dierti.in中读入数据。
输入第大器晚成行三个整数?表示数列的尺寸。
之后后生可畏行?个整数,第?个整数表示数列的第?项??。 输出格式:
输出到文件dierti.out中。
?行,第?行表示第?个询问的答案对1000000007取模的结果。 输入输出样例
输入样例#1: 3 1 2 4 输出样例#1: 30 表明 对于75%的数码,1 ≤ ? ≤ 10, 1
≤ ?? ≤ 10 对于此外伍分之一的多少,1 ≤ ? ≤ 1000, ?? = 1 4 对此十分之九的数据,1 ≤ ?
≤ 1000, 1 ≤ ?? ≤ 105 对于100%的数目,1 ≤ ? ≤ 100000, 1 ≤ ?? ≤ 109 T2

 

率先眼:DP,非常不得做。。

第二眼:三分之一的暴力好像能够搞生机勃勃搞

其三眼:其他伍分之一的多寡好像可以用组合数搞风度翩翩搞

其三眼:最终十分三不用了,开端搞吧,

 

于是噼里啪啦敲完第黄金时代题的鬼畜代码(就是落到实处个加减法作者连队列都用上了,,,,)

下一场最早搞其余五分二,其实此时剩下的时刻已经不多了,于是想也没想就直接暴力就组合数。

暴力敲的应当是没有错,但是因为求组合数牵扯到除法何况这道题还要取mod,这个时候想到须求求逆元精晓则当时也就还剩十几分钟所以果断舍弃

新生有大佬说全部都以生龙活虎的图景只要把全体数的平方全加起来再加个如何事物就足以,,,,,

 

正解:动规,用f[i]表示第i轮的持有意况的和,然后就不会了,,,,

暴力:

 

澳门新葡萄京官网注册 5 1
#include<iostream> 2 #include<cstdio> 3
#include<cstring> 4 #include<algorithm> 5
#include<queue> 6 using namespace std; 7 const int MAXN=100001; 8
const int maxn=0x7ffff; 9 const int mod=1000000007; 10 void read(int &n)
11 { 12 char c=’+’;int x=0;bool flag=0; 13
while(c<‘0’||c>’9′){c=getchar();if(c==’-‘)flag=1;} 14
while(c>=’0’&&c<=’9’) 15
x=(x<<1)+(x<<3)+c-48,c=getchar(); 16 flag==1?n=-x:n=x; 17 }
18 int n; 19 int a[MAXN]; 20 int flag=0; 21 int ans; 22 int
how[MAXN]; 23 int num=1; 24 int tot=0; 25 void calc() 26 { 27
queue<int>q; 28 for(int i=1;i<=num;i++) 29 { 30 if(how[i]==2)
31 { 32 int now=1; 33 while(how[i]==2) 34 { 35 now=(now*a[i])%mod;
36 i++; 37 } 38 now=(now*a[i])%mod; 39 q.push(now); 40 } 41 else 42
q.push(a[i]); 43 } 44 while(q.size()!=0) 45 { 46
ans=(ans+q.front())%mod; 47 q.pop(); 48 } 49 } 50 void dfs(int pos) 51 {
52 if(pos==n-1) 53 { 54 tot++; 55 calc(); 56 return ; 57 } 58 59 for(int
i=1;i<=2;i++) 60 { 61 how[num++]=i; 62 dfs(pos+1); 63
how[–num]=0; 64 } 65 } 66 int jc(int num) 67 { 68 if(num==0) 69
return 1; 70 else 71 return (num*(jc(num-1)))%mod; 72 } 73 int main()
74 { 75 freopen(“dierti.in”,”r”,stdin); 76
freopen(“dierti.out”,”w”,stdout); 77 read(n); 78 for(int
i=1;i<=n;i++) 79 { read(a[i]); if(a[i]==1卡塔尔 flag++; } 80
if(flag==n卡塔尔(قطر‎ 81 { 82 int p=jc(n-1卡塔尔国%mod; 83 for(int i=1;i<=n-1;i++卡塔尔国//
放多少个* 84 { 85 int hh=(p/(jc(i)*jc(n-i-1)))%mod; 86
ans=ans+((n-i)*hh)%mod; 87 } 88 printf(“%d”,(ans+n)%mod); 89 } 90 else
91 { 92 dfs(0); 93 printf(“%d”,ans%mod); 94 } 95 return 0; 96 } T2暴力

 

澳门新葡萄京官网注册 6 1
#include<bits/stdc++.h> 2 #define mod 1000000007 3 #define N
100010 4 using namespace std; 5 int T,n,i,a[N],g[N],f[N],sum,sum1;
6 int powmod(int x,int y){ 7 int ans=1; 8
for(;y;y>>=1,x=1ll*x*x%mod) 9 if(y&1)ans=1ll*ans*x%mod; 10
return ans; 11 } 12 int main(){ 13 scanf(“%d”,&n); 14
sum=0;sum1=g[0]=1; 15 for(i=1;i<=n;i++){ 16 scanf(“%d”,&a[i]); 17
g[i]=1ll*g[i-1]*a[i]%mod; 18 f[i]=(sum+1ll*g[i]*sum1)%mod;
19 sum=(sum+f[i])%mod; 20
sum1=(sum1+1ll*powmod(2,(i-1))*powmod(g[i],mod-2))%mod; 21 } 22
printf(“%dn”,f[n]); 23 } T2正解

 

 

 

T3

 

澳门新葡萄京官网注册 7标题叙述有多少个? * ?的网格图,在那之中各样格子都有叁个数。
设??为第?行的微小值,??为第?列的最大值,大家称三个网格是好的,当
且仅当满意 max(?1, …,??卡塔尔 = min(??, …,??卡塔尔国今后问起码修正多少个数能够使得这些网格是好的。 输入输出格式 输入格式:
从文件disanti.in中读入数据。 第豆蔻梢头行三个整数?。
之后?行,每行?个数,描述那几个矩阵。 输出格式: 输出到文件disanti.out中。
一个数???,表示最少需求改变的数的个数。 输入输出样例 暂时未有测试点 说明对于十分之六的多寡,1 ≤ ?, ?? ≤ 10 对于其余百分之三十的数量,1 ≤ ? ≤ 100, 1 ≤ ?? ≤ 3
对此八成的数目,1 ≤ ? ≤ 100, 1 ≤ ?? ≤ 105 对此100%的数额,1 ≤ ? ≤ 1000, 1
≤ ?? ≤ 10 T3

 

这题,,是自个儿平素骗的最康健的、

说一下自个儿的思绪:

当n>100时,cout<<rand();

else cout<<2;

然后,就得了20分。

为啥是2不是3吗?

笔者们想,对于三个n<=10的矩阵,

改叁次会不会太少了?

所以

改两次!

 

正解:大家固然叁个i是要找的答案。

那么那个i就要满意&……¥*……(&(*#@!&#(*@……¥(*&#%2

 

 

澳门新葡萄京官网注册 8 1
#include<iostream> 2 #include<cstdio> 3
#include<cstring> 4 #include<algorithm> 5
#include<queue> 6 using namespace std; 7 const int MAXN=1001; 8
const int maxn=0x7ffff; 9 void read(int &n) 10 { 11 char c=’+’;int
x=0;bool flag=0; 12
while(c<‘0’||c>’9′){c=getchar();if(c==’-‘)flag=1;} 13
while(c>=’0’&&c<=’9’) 14
x=(x<<1)+(x<<3)+c-48,c=getchar(); 15 flag==1?n=-x:n=x; 16 }
17 int map[MAXN][MAXN]; 18 int main() 19 { 20
freopen(“disanti.in”,”r”,stdin); 21 freopen(“disanti.out”,”w”,stdout);
22 int n; 23 read(n); 24 for(int i=1;i<=n;i++) 25 for(int
j=1;j<=n;j++) 26 read(map[i][j]); 27 if(n<=10) 28 printf(“2”);
29 else if(n<=100&&n<=1000) 30 printf(“20”); 31 else 32
printf(“200”); 33 return 0; 34 } 骗分

 

澳门新葡萄京官网注册 9 1
#include<bits/stdc++.h> 2 using namespace std; 3 int
n,m,i,x,A[1100],B[1100],C[1100000],ans,j,k,SS[1100000],TT[1100000];
4 pair<int,int>a[1100000]; 5 int main(){ 6 scanf(“%d”,&n); 7
m=n*n; 8 ans=n*2-1; 9 for(i=0;i<m;i++) 10
scanf(“%d”,&a[i].first),a[i].second=i; 11 sort(a,a+m); 12
for(i=0;i<m;i=j){ 13 TT[i]=TT[i-1]; 14
for(j=i;a[j].first==a[i].first&&j<m;j++){ 15 x=a[j].second; 16
B[x%n]++; 17 TT[i]=max(TT[i],B[x%n]); 18 } 19
for(k=i;k<j;k++)TT[k]=TT[i]; 20 } 21 memset(A,0,sizeof(A)); 22
for(i=m-1;i>=0;i=j){ 23 SS[i]=SS[i+1]; 24
for(j=i;a[j].first==a[i].first&&j>=0;j–){ 25 x=a[j].second; 26
A[x/n]++; 27 SS[i]=max(SS[i],A[x/n]); 28 } 29
for(k=i;k>j;k–)SS[k]=SS[i]; 30 } 31 for(i=0;i<m;i++) 32
if(n-SS[i]+n-TT[i]<ans)ans=n-SS[i]+n-TT[i]; 33
printf(“%dn”,ans); 34 } T3

 

 

 

 

总结:

还算考的不利,但此番考试能得rank5,运气成分真的是可怜的大。

T1有七三个人A掉,

T2有一人A掉 ,五几个90分,

证实自身的晋升空间还超大。

加油!

2017 noip 创建神迹!

 

 

忖度分数: 60+30+0=90=划水 实际分数: 90+30+20=140=rank5=雷蛇鼠标
一句话计算:昨日该买彩票…

DFS   先导的时候回朔难题并未有思虑清楚

此代码在全为-2时,输出0,分明错误,因为函数下标从0从前,而传递的参数希望他从1开头

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int stick[22];
int k[22];
int n,sum,average,temp;

#include<stdio.h>
#include<string.h>
int a[101][101],b[10010];
int subsequencesum(int a[],int n)
{
 int sum=0,maxsum=0,i;
 for(i=0;i<n;i++)
 {
  sum+=a[i];
  if(sum>maxsum)
   maxsum=sum;  
  else
   if(sum<0)
    sum=0;
 }
 return maxsum;
}
int main()
{
 int i,j,T,p,k;int col,row,m;int max,ans,sum,cnt;
 scanf(“%d”,&T);
 while(T–)
 {
  max=-0x7fffffff,ans=-0x7fffffff;
  memset(a,0,sizeof(a));
  scanf(“%d%d”,&row,&col);
  for(i=1;i<=row;i++)
   for(j=1;j<=col;j++)
    scanf(“%d”,&a[i][j]);
  for(i=1;i<=row;i++)
  {
   memset(b,0,sizeof(b));
   cnt=1;;
   for(j=i;j<=row;j++)
    {
     for(k=i;k<=j;k++)  
      {
       sum=0;
       for(m=1;m<=col;m++)
       sum+=a[k][m];
       b[cnt++]=sum;
      }
    }
   max=subsequencesum(b,cnt-1);
   if(ans<max)
    ans=max;
  }
  printf(“%dn”,ans);
 }
  return 0;
}
   

int cmp ( const void *a , const void *b )
{
 return *(int *)b – *(int *)a;
}

 

void dfs(int numbers,int sticks,int real_time_sum)
{
 int i;
 if(sticks==3)
 {
  temp=1;
  return;
 }
 for(i=numbers;i<n&&!temp;i++)
 {
  if(k[i]==0)
  {
   k[i]=1;
            if(real_time_sum + stick[i] == average)
   {
    dfs(0, sticks + 1, 0);
            }
            else if(real_time_sum + stick[i] < average)
   {
                dfs(i+1,sticks, real_time_sum + stick[i]);
            }
   k[i]=0;
        }
 }
 return;
}
void main()
{
    int t,max,i;
 scanf(“%d”,&t);
    while(t–)
 {
        memset(stick,0,sizeof(stick));
        memset(k,0,sizeof(k));
  scanf(“%d”,&n);
  sum=0;
  max=0;
        for(i=0;i<n;i++)
  {
   scanf(“%d”,&stick[i]);
            sum+=stick[i];
   if(stick[i]>max)
    max=stick[i];
        }
        if(sum%4||sum/4<max)
  {
   printf(“non”);
            continue;
        }
        average=sum/4;
  qsort(stick,n,sizeof(stick[0]),cmp);
  temp=0;dfs(0,0,0);
        if(temp)
   printf(“yesn”);
        else
   printf(“non”);
    }
}

 

//修改后,超时,确实麻烦啦
#include<stdio.h>
#include<string.h>
int a[101][101],b[10010];
int subsequencesum(int a[],int n)
{
 int sum=0,maxsum=-0x7fffffff,i;
 for(i=0;i<n;i++)
 {
  sum+=a[i+1];
  if(sum>maxsum)
   maxsum=sum;  
  else
   if(sum<0)
    sum=0;
 }
 return maxsum;
}
int main()
{
 int i,j,T,p,k;int col,row,m;int max,ans,sum,cnt;
 scanf(“%d”,&T);
 while(T–)
 {
  max=-0x7fffffff,ans=-0x7fffffff;
  memset(a,0,sizeof(a));
  scanf(“%d%d”,&row,&col);
  for(i=1;i<=row;i++)
   for(j=1;j<=col;j++)
    scanf(“%d”,&a[i][j]);
  for(i=1;i<=row;i++)
  {
   cnt=1;
   for(j=i;j<=row;j++)
    {
     //memset(b,0,sizeof(b));
     for(k=i;k<=j;k++)  
      {
       sum=0;
       for(m=1;m<=col;m++)
       sum+=a[k][m];
      // printf(“%dn”,sum);
       b[cnt++]=sum;
      }
     max=subsequencesum(b,cnt-1);
      //printf(“%d   %d     %dn”,sum,max,ans);
     if(ans<max)
      ans=max;
    }
  }
  printf(“%dn”,ans);
 }
 return 0;
}
   

 

//改成函数调用也过期

//改善后,超时,确实麻烦啦
#include<stdio.h>
#include<string.h>
int a[101][101],b[10010];
int cnt,col,row;
int subsequencesum(int a[],int n)
{
 int sum=0,maxsum=-0x7fffffff,i;
 for(i=0;i<n;i++)
 {
  sum+=a[i+1];
  if(sum>maxsum)
   maxsum=sum;  
  else
   if(sum<0)
    sum=0;
 }
 return maxsum;
}
void total(int i,int j)
{
 int sum,k,m;
 for(k=i;k<=j;k++)  
 {
  sum=0;
  for(m=1;m<=col;m++)
   sum+=a[k][m];
  b[cnt++]=sum;
 }
}
int main()
{
 int i,j,T,p,k;int m;int max,ans,sum;
 scanf(“%d”,&T);
 while(T–)
 {
  max=-0x7fffffff,ans=-0x7fffffff;
  memset(a,0,sizeof(a));
  scanf(“%d%d”,&row,&col);
  for(i=1;i<=row;i++)
   for(j=1;j<=col;j++)
    scanf(“%d”,&a[i][j]);
  for(i=1;i<=row;i++)
  {
   cnt=1;
   for(j=i;j<=row;j++)
    {
     //memset(b,0,sizeof(b));
     total(i,j);
     max=subsequencesum(b,cnt-1);
      //printf(“%d   %d     %dn”,sum,max,ans);
     if(ans<max)
      ans=max;
    }
  }
  printf(“%dn”,ans);
 }
 return 0;
}
   

 

 

 

 

 

//AC 

#include<stdio.h>
#include<string.h>
int a[101][101],b[101];
int subsequencesum(int a[],int n)
{
 int sum=0,maxsum=-0x7fffffff,i;
 for(i=1;i<=n;i++)
  if(maxsum<a[i])
   maxsum=a[i];
 if(maxsum<=0)
  return maxsum;
 for(i=0;i<n;i++)
 {
  sum+=a[i+1];
  if(sum>maxsum)
   maxsum=sum;  
  else
   if(sum<0)
    sum=0;
 }
 return maxsum;
}     
int main()
{
   int col,row,max,ans,temp;int i,j,k,T,m;
   scanf(“%d”,&T);
   while(T–)
  {
     temp=ans=max=-0x7fffffff;
     scanf(“%d%d”,&row,&col);
     for(i=1;i<=row;i++)
      for(j=1;j<=col;j++)
       scanf(“%d”,&a[i][j]);
     for(i=1;i<=row;i++)
     {      
       memset(b,0,sizeof(b));
       for(j=i;j<=row;j++)
       {
          for(k=1;k<=col;k++)
          {
           b[k]+=a[j][k];
          }
          ans=subsequencesum(b,col);
         if(temp<ans)
          temp=ans;
       }
     }
     printf(“%dn”,temp);
  }
  return 0;
}