View Code of Problem 3569

#include<stdio.h>
int calc(int num[],int begin,int end)
{
	int sum=0;
	for(int i=begin;i<=end;i++)
		sum+=num[i];
	return sum;
}
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 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&&l<len;)
				{
					if(!b||num[l]>=0||l<len-1&&max+num[l]>=num[l+1])
					{
						int tmp=calc(num,k,l);
						if(tmp>max&&b||!b)
						{
							max=tmp;
							b=1;
						}
						l++;
					}
					else
					{
						k=l+1;
						l=k;
					}
				}
			}
		}
		printf("%d\n",max);
	}
	return 0;
}

Double click to view unformatted code.


Back to problem 3569