Cod sursa(job #1081829)
Utilizator | Data | 13 ianuarie 2014 22:03:50 | |
---|---|---|---|
Problema | Zone | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 2.65 kb |
#include<cstdio>
#include<algorithm>
using namespace std;
long long k,p,u,m,v,i1,i2,j3,j2,i,j,n;
long long z[12],vec[12],s[515][515],a[515][515];
long long suma(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("%lld",&n);
for(i=1;i<=9;i++)
scanf("%lld",&vec[i]);
sort(vec+1,vec+9+1);
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
scanf("%lld",&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(j3=1;j3<n-1;j3++)
{
v=suma(1,1,i1,j3);
p=1;
u=9;
while(p<=u)
{
m=(p+u)/2;
if(vec[m]>v) u=m-1;
else
if(vec[m]<v) p=m+1;
else break;
}
if(p<=u)
{
for(i2=i1+1;i2<n;i2++)
{
p=1;
u=9;
v=suma(i1+1,1,i2,j3);
while(p<=u)
{
m=(p+u)/2;
if(vec[m]>v) u=m-1;
else
if(vec[m]<v) p=m+1;
else break;
}
if(p<=u)
{
for(j2=j3+1;j2<n;j2++)
{
z[1]=suma(1,1,i1,j3);
z[2]=suma(i1+1,1,i2,j3);
z[3]=suma(i2+1,1,n,j3);
z[4]=suma(1,j3+1,i1,j2);
z[5]=suma(i1+1,j3+1,i2,j2);
z[6]=suma(i2+1,j3+1,n,j2);
z[7]=suma(1,j2+1,i1,n);
z[8]=suma(i1+1,j2+1,i2,n);
z[9]=suma(i2+1,j2+1,n,n);
sort(z+1,z+9+1);
for(k=1;k<=9;k++)
if(z[k]!=vec[k]) break;
if(k>9)
{
printf("%lld %lld %lld %lld\n",i1,i2,j3,j2);
return 0;
}
}
}
}
}
}
return 0;
}