Cod sursa(job #76397)

Utilizator sealTudose Vlad seal Data 9 august 2007 17:28:45
Problema Zone Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.72 kb
using namespace std;
#include<cstdio>
#include<algorithm>
#define Nm 513
int A[Nm][Nm],n,l1b,l2b,c1b,c2b;
long long M[Nm][Nm],S[9];

void read()
{
    int i,j;

    freopen("zone.in","r",stdin);
    scanf("%d",&n);
    for(i=0;i<9;++i)
        scanf("%lld",S+i);
    for(i=1;i<=n;++i)
        for(j=1;j<=n;++j)
            scanf("%d",&A[i][j]);
}

void solve()
{
    int L2[9],C2[9],nrl2,nrc2,i,j,l1,l2,c1,c2;
    long long S2[9];

    sort(S,S+9);

    for(i=1;i<=n;++i)
        for(j=1;j<=n;++j)
            M[i][j]=M[i-1][j]+M[i][j-1]-M[i-1][j-1]+A[i][j];

    for(l1=1;l1<n-1;++l1)
    {
        i=0;
        for(c1=1;c1<n-1;++c1)
        {
            while(i<9 && M[l1][c1]>S[i])
                ++i;
            if(i==9)
                break;
            if(M[l1][c1]<S[i])
                continue;
            nrl2=0; j=0;
            for(l2=l1+1;l2<n;++l2)
            {
                while(j<9 && M[l2][c1]-M[l1][c1]>S[j])
                    ++j;
                if(j==9)
                    break;
                if(M[l2][c1]-M[l1][c1]==S[j])
                    L2[nrl2++]=l2;
            }
            nrc2=0; j=0;
            for(c2=c1+1;c2<n;++c2)
            {
                while(j<9 && M[l1][c2]-M[l1][c1]>S[j])
                    ++j;
                if(j==9)
                    break;
                if(M[l1][c2]-M[l1][c1]==S[j])
                    C2[nrc2++]=c2;
            }
            for(l2=0;l2<nrl2;++l2)
            {
                for(c2=0;c2<nrc2;++c2)
                {
                    S2[0]=S[i];
                    S2[1]=M[l1][C2[c2]]-M[l1][c1];
                    S2[2]=M[l1][n]-M[l1][C2[c2]];
                    S2[3]=M[L2[l2]][c1]-M[l1][c1];
                    S2[4]=M[L2[l2]][C2[c2]]-M[L2[l2]][c1]-M[l1][C2[c2]]+M[l1][c1];
                    S2[5]=M[L2[l2]][n]-M[L2[l2]][C2[c2]]-M[l1][n]+M[l1][C2[c2]];
                    S2[6]=M[n][c1]-M[L2[l2]][c1];
                    S2[7]=M[n][C2[c2]]-M[L2[l2]][C2[c2]]-M[n][c1]+M[L2[l2]][c1];
                    S2[8]=M[n][n]-M[L2[l2]][n]-M[n][C2[c2]]+M[L2[l2]][C2[c2]];
                    sort(S2,S2+9);
                    if(!memcmp(S,S2,sizeof(S)))
                        break;
                }
                if(c2<nrc2)
                    break;
            }
            if(l2<nrl2 && (!l1b || L2[l2]<l2b))
            {
                l1b=l1;
                l2b=L2[l2];
                c1b=c1;
                c2b=C2[c2];
            }
        }
        if(l1b)
           break;
    }
}

void write()
{
    freopen("zone.out","w",stdout);
    printf("%d %d %d %d\n",l1b,l2b,c1b,c2b);
}

int main()
{
    read();
    solve();
    write();
    return 0;
}