Cod sursa(job #1052956)

Utilizator enedumitruene dumitru enedumitru Data 11 decembrie 2013 22:37:31
Problema Zone Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.38 kb
#include<fstream>
#include<algorithm>
#define ll long long
using namespace std;
ifstream f("zone.in"); ofstream g("zone.out");
int n,i,j,l1,l2,c1,c2,ok,a;
ll sum,v[10],r[10],s[513][513];
ll suma(int x1, int y1, int x2, int y2)
{	return s[x2][y2]+s[x1][y1]-s[x2][y1]-s[x1][y2];} 
void caut()
{ 	int st=1,dr=9;
	while(st<=dr)
	{	int mij=(st+dr)>>1;
		if(v[mij]==sum) {ok=1; return;}
		if(v[mij]>sum) dr=mij-1; else st=mij+1;
	}
}
int main()
{	f>>n;
	for(i=1; i<=9; i++)	f>>v[i];
	sort(v+1,v+10);
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++)
			{f>>a; s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a;}
	for(l1=1;l1<n-1;l1++)
	{	for(c1=1;c1<n-1;c1++)
		{	sum=suma(0,0,l1,c1); ok=0; caut();
			if(ok)
			{	for(l2=l1+1; l2<n-1;  l2++)
				{	sum=suma(l1,0,l2,c1); ok=0; caut();
					if(ok) 
					{	for(c2=c1+1; c2<n-1; c2++)
						{	sum=suma(0,c1,l1,c2);  ok=0; caut();
							if(ok)
							{	r[1]=suma(0,0,l1,c1); 
								r[2]=suma(0,c1,l1,c2); 
								r[3]=suma(0,c2,l1,n);
								r[4]=suma(l1,0,l2,c1);
								r[5]=suma(l1,c1,l2,c2); 
								r[6]=suma(l1,c2,l2,n);  
								r[7]=suma(l2,0,n,c1);  
								r[8]=suma(l2,c1,n,c2); 
								r[9]=suma(l2,c2,n,n);
								sort(r+1,r+10);
								for(i=1; i<=9; i++)
									if(r[i]!=v[i]) ok=0;
								if(ok) {g<<l1<<" "<<l2<<" "<<c1<<" "<<c2; g.close(); return 0;} 
							}
						}
					} 
				}
			}   
		}
	}
}