Cod sursa(job #1417128)

Utilizator felixiPuscasu Felix felixi Data 9 aprilie 2015 17:29:41
Problema Zone Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.94 kb
#include<fstream>
#include<algorithm>

using namespace std;

ifstream f("zone.in");
ofstream g("zone.out");

typedef long long I64;

int n, i, j, l1, l2, c1, c2, ok, a;

I64 sum, v[10], r[10], s[513][513];

I64 suma(int x1, int y1, int x2, int y2)
{   return s[x2][y2] + s[x1][y1] - s[x2][y1] - s[x1][y2];}

void BS()
{   int st=1, dr=9;
    while(st<=dr)
    {   int mij=(st+dr)/2;
        if(v[mij]==sum) {ok=1; return;}
        if(v[mij]>sum) dr=mij-1;
        else st=mij+1;
    }
}

int main()
{   f>>n;
    for(i=1; i<=9; i++)  f>>v[i];

    sort(v+1,v+10);
    for(i=1; i<=n; i++)
        for(j=1;j<=n;j++)
            {f>>a; s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a;}

    for(l1=1;l1<n-1;l1++)
        for(c1=1;c1<n-1;c1++)
        {   sum=suma(0,0,l1,c1); ok=0; BS();
            if(ok)
                for(l2=l1+1; l2<n-1;  l2++)
                {   sum=suma(l1,0,l2,c1); ok=0; BS();
                    if(ok)
                        for(c2=c1+1; c2<n-1; c2++)
                        {   sum=suma(0,c1,l1,c2);  ok=0; BS();
                            if(ok)
                            {   r[1]=suma(0,0,l1,c1);
                                r[2]=suma(0,c1,l1,c2);
                                r[3]=suma(0,c2,l1,n);
                                r[4]=suma(l1,0,l2,c1);
                                r[5]=suma(l1,c1,l2,c2);
                                r[6]=suma(l1,c2,l2,n);
                                r[7]=suma(l2,0,n,c1);
                                r[8]=suma(l2,c1,n,c2);
                                r[9]=suma(l2,c2,n,n);
                                sort(r+1,r+10);

                                for(i=1; i<=9; i++)
                                    if(r[i]!=v[i]) ok=0;
                                if(ok) {g<<l1<<" "<<l2<<" "<<c1<<" "<<c2; g.close(); return 0;}
                            }
                        }
                }
        }
    return 0;
}