Cod sursa(job #741726)

Utilizator geniucosOncescu Costin geniucos Data 26 aprilie 2012 20:25:10
Problema Zone Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.64 kb
#include<cstdio>
#include<algorithm>
using namespace std;
long long k,p,u,m,v,i1,i2,j1,j2,i,j,n,z[12],vec[12],s[515][515],a[515][515];
long long 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("%lld",&n);
for(i=1;i<=9;i++)
	scanf("%lld",&vec[i]);
sort(vec+1,vec+9+1);
for(i=1;i<=n;i++)
	for(j=1;j<=n;j++)
		scanf("%lld",&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++)
			{
				p=1;
				u=9;
				v=sum(i1+1,1,i2,j1);
				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(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("%lld %lld %lld %lld\n",i1,i2,j1,j2);
							return 0;
						}
					}
				}
			}
		}
	}
return 0;
}