Cod sursa(job #741722)

Utilizator geniucosOncescu Costin geniucos Data 26 aprilie 2012 20:20:18
Problema Zone Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.38 kb
#include<cstdio>
#include<algorithm>
using namespace std;
int k,p,u,m,v,i1,i2,j1,j2,i,j,n,z[12],vec[12],s[515][515],a[515][515];
int sum(int x1,int y1,int x2,int y2)
{
	return s[x2][y2]-s[x2][y1-1]-s[x1-1][y2]+s[x1-1][y1-1];
}
int main()
{
freopen("zone.in","r",stdin);
freopen("zone.out","w",stdout);
scanf("%d",&n);
for(i=1;i<=9;i++)
	scanf("%d",&vec[i]);
sort(vec+1,vec+9+1);
for(i=1;i<=n;i++)
	for(j=1;j<=n;j++)
		scanf("%d",&a[i][j]);
s[1][1]=a[1][1];
for(i=2;i<=n;i++)
	s[i][1]=s[i-1][1]+a[i][1];
for(j=2;j<=n;j++)
	s[1][j]=s[1][j-1]+a[1][j];
for(i=2;i<=n;i++)
	for(j=2;j<=n;j++)
		s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j];
for(i1=1;i1<n-1;i1++)
	for(j1=1;j1<n-1;j1++)
	{
		v=sum(1,1,i1,j1);
		p=1;
		u=9;
		while(p<=u)
		{
			m=(p+u)/2;
			if(vec[m]>v) u=m-1;
			else
			if(vec[m]<v) p=m+1;
			else break;
		}
		if(p<=u)
		{
			for(i2=i1+1;i2<n;i2++)
				for(j2=j1+1;j2<n;j2++)
				{
					z[1]=sum(1,1,i1,j1);
					z[2]=sum(i1+1,1,i2,j1);
					z[3]=sum(i2+1,1,n,j1);
					z[4]=sum(1,j1+1,i1,j2);
					z[5]=sum(i1+1,j1+1,i2,j2);
					z[6]=sum(i2+1,j1+1,n,j2);
					z[7]=sum(1,j2+1,i1,n);
					z[8]=sum(i1+1,j2+1,i2,n);
					z[9]=sum(i2+1,j2+1,n,n);
					sort(z+1,z+9+1);
					for(k=1;k<=9;k++)
						if(z[k]!=vec[k]) break;
					if(k>9)
					{
						printf("%d %d %d %d\n",i1,i2,j1,j2);
						return 0;
					}
			}
		}
	}
return 0;
}