Cod sursa(job #34754)

Utilizator DITzoneCAdrian Diaconu DITzoneC Data 21 martie 2007 12:38:11
Problema Zone Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.5 kb
#include <stdio.h>
#include <algorithm>

using namespace std;

typedef long long lint;

#define nmax 512
#define pt(i) (1<<(i))
#define FOR(i,s,d) for(i=(s);i<(d);++i)

lint B[9],A[nmax][nmax],C[9];
int n,sl1=513,sl2,sc1,sc2;

int findc(int z,lint x)
{
	int i,j=0;
	for(i=8;i>=0;--i)
		if(j+pt(i)<n&&A[j+pt(i)][z]<=x)
			j+=pt(i);
	return A[j][z]==x?j:-1;
}

int findl(int z,lint x)
{
	int i,j=0;
	for(i=8;i>=0;--i)
		if(j+pt(i)<n&&A[z][j+pt(i)]<=x)
			j+=pt(i);
	return A[z][j]==x?j:-1;
}

int main()
{
	int i,j,k,t,l1,l2,c1,c2;
	freopen("zone.in","r",stdin);
	freopen("zone.out","w",stdout);
	scanf("%d",&n);
	FOR(i,0,9)
		scanf("%lld",&B[i]);
	sort(B,B+9);
	FOR(i,0,n) FOR(j,0,n)
	{
		scanf("%lld",&A[i][j]);
		if(i)
			A[i][j]+=A[i-1][j];
		if(j)
			A[i][j]+=A[i][j-1];
		if(i&&j)
			A[i][j]-=A[i-1][j-1];
	}
	FOR(c1,0,n) FOR(j,0,9) FOR(k,0,9) FOR(t,0,9)
	{
		if(j==k||j==t||k==t)
			continue;
		l1=findc(c1,B[j]);
		l2=findc(c1,B[j]+B[k]);
		if(l1==-1||l2==-1)
			continue;
		c2=findl(l1,B[j]+B[t]);
		if(c2==-1)
			continue;		
		C[0]=B[j],C[1]=B[t],C[2]=A[l1][n-1]-A[l1][c2];
		C[3]=B[k],C[4]=A[l2][c2]-A[l2][c1]-C[1],C[5]=A[l2][n-1]-A[l2][c2]-C[2];
		C[6]=A[n-1][c1]-A[l2][c1],C[7]=A[n-1][c2]-A[l2][c2]-C[6],C[8]=A[n-1][n-1]-A[l2][n-1]-C[6]-C[7];
		sort(C,C+9);
		FOR(i,0,9)
			if(C[i]!=B[i])
				break;
		if(i!=9)
			continue;
		if(l1<sl1||(l1==sl1&&c1<sc1)||(l1==sl1&&c1==sc1&&l2<sl2)||
				(l1==sl1&&l2==sl2&&c1==sc1&&c2<sl2))
			sl1=l1,sl2=l2,sc1=c1,sc2=c2;
	}
	printf("%d %d %d %d\n",sl1+1,sl2+1,sc1+1,sc2+1);	
	return 0;
}