Cod sursa(job #590259)

Utilizator veleanduAlex Velea veleandu Data 16 mai 2011 08:44:24
Problema Zone Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.51 kb
#include<fstream>
#include<iostream>
using namespace std;
long long l1,l2,c1,c2;
long long  P[50],S[50],p;
long long SUM[520][520];
long T[520][520];
long n;
long i,j,ok,k;
long CBC(long l1, long st, long dr, long val)
{
    long c1;
    if(st<=dr)
        ;
    else
        return st;
    c1=st+(dr-st)/2;
    if(SUM[l1][c1]==val)
        return c1;
    if(SUM[l1][c1]>val)
        return CBC(l1,st,c1-1,val);
    return CBC(l1,c1+1,dr,val);
}

long CBL(long c1, long st, long dr, long val)
{
    long l2;
    if(st<=dr)
        ;
    else
        return st;
    l2=st+(dr-st)/2;
    long x;
    x=SUM[l2][c1];
    if(x==val)
        return l2;
    if(x>val)
        return CBL(c1,st,l2-1,val);
    return CBL(c1,l2+1,dr,val);
}


int main()
{
    freopen("zone.in","r",stdin);
    freopen("zone.out","w",stdout);
    scanf("%d", &n);
    for(i=1; i<=9; ++i)
        scanf("%d", &S[i]);
    sort(S+1,S+10);
    for(i=1; i<=n; ++i)
        for(j=1; j<=n; ++j)
            scanf("%d", &T[i][j]);
    for(i=1; i<=n; ++i)
        for(j=1; j<=n; ++j)
            SUM[i][j]=SUM[i-1][j]+SUM[i][j-1]-SUM[i-1][j-1]+T[i][j];
/*	for(i=1; i<=5; ++i,printf("\n"))
	{
		for(j=1; j<=5; ++j)
			printf("%d ",SUM[i][j]);
	}*/
	sort(S+1,S+10);
	for( i=1; i<=9; ++i)
	{
		for( l1=1; l1<=n-2; ++l1)
		{
			c1=CBC(l1,1,n-2,S[i]);
			if(SUM[l1][c1]==S[i])
				for( j=1; j<=9; ++j)
				if(i!=j)
					{
						c2=CBC(l1,c1+1,n-1,S[i]+S[j]);
						if(SUM[l1][c2]==S[i]+S[j])
						{
							for( k=1; k<=9; ++k)
								if(k!=i && k!=j)
								{	
									l2=CBL(c1,l1+1,n-1,S[i]+S[k]); // 69 + 69 = 138
									if(SUM[l2][c1]==S[i]+S[k])
									{
										P[1]=S[i];
										P[2]=S[j];
										P[3]=S[k];
										P[4]=SUM[l1][n]-SUM[l1][c2];
										P[5]=SUM[l2][c2]+SUM[l1][c1]-SUM[l2][c1]-SUM[l1][c2];
										P[6]=SUM[l2][n]+SUM[l1][c2]-SUM[l2][c2]-SUM[l1][n];
										P[7]=SUM[n][c1]-SUM[l2][c1];
										P[8]=SUM[n][c2]+SUM[l2][c1]-SUM[l2][c2]-SUM[n][c1];
										P[9]=SUM[n][n]+SUM[l2][c2]-SUM[n][c2]-SUM[l2][n];
										/*printf("%d %d %d %d         ",l1,l2,c1,c2);
										for(p=1; p<=9; ++p)
											printf("%d ",P[p]);
										printf("\n\n"); */
										sort(P+1,P+10);
										ok=1;
										for(p=1; p<=9; ++p)
											if(S[p]!=P[p])
												ok=0;
										if(ok)
										{
											printf("%d %d %d %d\n",l1,l2,c1,c2);
											return 0;
										}
									}
								}
						}
					
					}
		} 
	}
    return 0;
}