Cod sursa(job #479069)
Utilizator | Eugenie Daniel Posdarascu eudanip | Data | 22 august 2010 15:46:18 |
---|---|---|---|
Problema | Zone | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 3.14 kb |
#include<stdio.h>
#include<algorithm>
using namespace std;
#define ll long long
int a[550][550],n;
ll s[550][550],z[13],v[13];
inline ll sp(int px1,int py1,int px2,int py2)
{
return (s[px2][py2]-s[px1-1][py2]-s[px2][py1-1]+s[px1-1][py1-1]);
}
int verifica(int l1,int l2,int c1,int c2)
{
int i;
z[1]=sp(1,1,l1,c1);
z[2]=sp(1,c1+1,l1,c2);
z[3]=sp(1,c2+1,l1,n);
z[4]=sp(l1+1,1,l2,c1);
z[5]=sp(l1+1,c1+1,l2,c2);
z[6]=sp(l1+1,c2+1,l2,n);
z[7]=sp(l2+1,1,n,c1);
z[8]=sp(l2+1,c1+1,n,c2);
z[9]=sp(l2+1,c2+1,n,n);
sort(z+1,z+10);
for(i=1;i<=9;i++)
if(z[i]!=v[i])
return 0;
return 1;
}
int main ()
{
int i,j,st,dr,c1,l1;
int l2,z1,z2,z3,mij;
ll sum;
freopen("zone.in","r",stdin);
freopen("zone.out","w",stdout);
scanf("%d",&n);
for(i=1;i<=9;i++)
scanf("%lld",&v[i]);
sort(v+1,v+10);
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
scanf("%d",&a[i][j]);
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j];
for(l1=1;l1<n-1;l1++)
for(z1=1;z1<=9;z1++)
{
st=1;dr=n;
while(st<=dr)
{
mij=(st+dr)/2;
sum=sp(1,1,l1,mij);
if(sum<v[z1])
st=mij+1;
else
if(sum>v[z1])
dr=mij-1;
else
break;
}
if(st>dr)
continue;
c1=mij;
for(z3=1;z3<=9;z3++)
{
if(z3==z1)
continue;
st=l1+1;dr=n;
while(st<=dr)
{
mij=(st+dr)/2;
sum=sp(l1+1,1,mij,c1);
if(sum<v[z3])
st=mij+1;
else
if(sum>v[z3])
dr=mij-1;
else
break;
}
if(st>dr)
continue;
l2=mij;
for(z2=1;z2<=9;z2++)
{
if(z2==z1 || z2==z3)
continue;
st=c1+1;dr=n;
while(st<=dr)
{
mij=(st+dr)/2;
sum=sp(1,c1+1,l1,mij);
if(sum<v[z2])
st=mij+1;
else
if(sum>v[z2])
dr=mij-1;
else
break;
}
if(st>dr)
continue;
if(verifica(l1,l2,c1,mij))
{
printf("%d %d %d %d\n",l1,l2,c1,mij);
return 0;
}
}//for z2
}//for z3
}// for z1
return 0;
}