Cod sursa(job #1081812)

Utilizator iordache.bogdanIordache Ioan-Bogdan iordache.bogdan Data 13 ianuarie 2014 21:57:32
Problema Zone Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.61 kb
#include<cstdio>
#include<algorithm>

using namespace std;

int k,p,u,m,v,i1,i2,j1,j2,i,j,n;
int z[12],vec[12],s[515][515],a[515][515];

int 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("%d",&n);
    for(i=1;i<=9;i++)
        scanf("%d",&vec[i]);
    sort(vec+1,vec+9+1);
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            scanf("%d",&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(j1=1;j1<n-1;j1++)
        {
            v=suma(1,1,i1,j1);
            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,j1);
                    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=j1+1;j2<n;j2++)
                        {
                            z[1]=suma(1,1,i1,j1);
                            z[2]=suma(i1+1,1,i2,j1);
                            z[3]=suma(i2+1,1,n,j1);
                            z[4]=suma(1,j1+1,i1,j2);
                            z[5]=suma(i1+1,j1+1,i2,j2);
                            z[6]=suma(i2+1,j1+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("%d %d %d %d\n",i1,i2,j1,j2);
                                return 0;
                            }
                        }
                    }
                }
            }
        }
    return 0;
}