Cod sursa(job #940414)

Utilizator BlackLordFMI Alex Oprea BlackLord Data 16 aprilie 2013 10:16:22
Problema Zone Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.71 kb
#include <fstream>
#include <algorithm>
using namespace std;
FILE*f=fopen("zone.in", "r");
FILE*g=fopen("zone.out", "w");
int n, i, j, l1, l2, c1, c2, p, u, m, ok, s1, s2, s3, L1, L2, C1, C2;
long long v[520][520], a[520][520], s[10], b[10];
bool viz[10];

int cbc1(){
    p=1;
    u=n-2;
    while(p<=u)
    {
        m=p+((u-p)>>1);
        if(a[l1][m]==s[s1])
            return m;
        if(a[l1][m]<s[s1])
            p=m+1;
        else
            u=m-1;
    }
    return 0;
}

int cbl2(){
    p=l1+1;
    u=n-1;
    while(p<=u)
    {
        m=p+((u-p)>>1);
        if(a[m][c1]-a[l1][c1]==s[s2])
            return m;
        if(a[m][c1]-a[l1][c1]<s[s2])
            p=m+1;
        else
            u=m-1;
    }
    return 0;
}

int cbc2(){
    p=c1+1;
    u=n-1;
    while(p<=u)
    {
        m=p+((u-p)>>1);
        if(a[l1][m]-a[l1][c1]==s[s3])
            return m;
        if(a[l1][m]-a[l1][c1]<s[s3])
            p=m+1;
        else
            u=m-1;
    }
    return 0;
}

void solutie(){
    b[1]=s[s1];
    b[2]=s[s3];
    b[3]=a[l1][n]-b[1]-b[2];
    b[4]=s[s2];
    b[5]=a[l2][c2]-b[1]-b[2]-b[4];
    b[6]=a[l2][n]-b[5]-b[4]-b[3]-b[2]-b[1];
    b[7]=a[n][c1]-b[4]-b[1];
    b[8]=a[n][c2]-b[1]-b[2]-b[4]-b[5]-b[7];
    b[9]=a[n][n]-b[1]-b[2]-b[3]-b[4]-b[5]-b[6]-b[7]-b[8];
    sort(b+1, b+10);
    bool ok=0;
    for(i=1; i<10; i++)
        if(s[i]!=b[i])
            ok=1;
    if(ok==0)
        if(L1+L2+C1+C2>l1+l2+c1+c2)
        {
            L1=l1;
            L2=l2;
            C1=c1;
            C2=c2;
        }
}

int main(){
	fscanf(f, "%d", &n);
    for(i=1; i<10; i++)
        fscanf(f, "%lld", &s[i]);
    for(i=1; i<=n; i++)
        for(j=1; j<=n; j++)
            fscanf(f, "%lld", &v[i][j]);
    sort(s+1, s+10);
    for(i=1; i<=n; i++)
        for(j=1; j<=n; j++)
            a[i][j]=v[i][j]+a[i-1][j]+a[i][j-1]-a[i-1][j-1];
    L1=5000;
    int N=n-1;
    for(l1=1; l1<N; l1++)
        for(s1=1; s1<10; s1++)
            if( !viz[s1] )
            {
                c1=cbc1();
                viz[s1]=1;
                for(s2=1; s2<10; s2++)
                    if( !viz[s2] )
                    {
                        l2=cbl2();
                        viz[s2]=1;
                        for(s3=1; s3<10; s3++)
                        {
                            if( !viz[s3] )
                            {
                                c2=cbc2();
                                solutie();
                            }
                        }
                        viz[s2]=0;
                    }
                viz[s1]=0;
            }
    fprintf(g, "%d %d %d %d", L1,L2, C1, C2);
    return 0;
}