View Code of Problem 3569

#include<stdio.h>
int make(int rect[100][100],int begin,int end,int len,int num[])
{
	for(int j=0;j<len;j++)
	{
		int sum=0;
		for(int i=begin;i<=end;i++)
		{
			sum+=rect[i][j];
		}
		num[j]=sum;
	}
	return 1;
}
int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		int max=0;
		int bb=0;
		int sum=0;
		int b=0;
		int len;
		int num[100];
		int rect[100][100];
		scanf("%d",&len);
		for(int i=0;i<len;i++)
			for(int j=0;j<len;j++)
				scanf("%d",rect[i]+j);
		for(int i=0;i<len;i++)
		{
			for(int j=i;j<len;j++)
			{
				make(rect,i,j,len,num);
				for(int k=0,l=0;k<len;)
				{
					sum=0;
					b=0;
					for(l=k;l<len;l++)
					{
						if(sum<=-num[i]&&b)break;
						b=1;
						sum+=num[l];
						if(sum>max||!bb)
						{
							max=sum;
							bb=1;
						}
					}
					k=l+1;
				}
			}
		}
		if(sum>max||!bb)
		{
			max=sum;
		}
		printf("%d\n",max);
	}
	return 0;
}

Double click to view unformatted code.


Back to problem 3569