Cod sursa(job #741720)

Utilizator geniucosOncescu Costin geniucos Data 26 aprilie 2012 20:15:18
Problema Zone Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.18 kb
#include<cstdio>
#include<algorithm>
using namespace std;
int i1,i2,j1,j2,i,j,p,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(i2=i1+1;i2<n;i2++)
		for(j1=1;j1<n-1;j1++)
			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(p=1;p<=9;p++)
					if(z[p]!=vec[p]) break;
				if(p>9)
				{
					printf("%d %d %d %d\n",i1,i2,j1,j2);
					return 0;
				}
			}
return 0;
}