Cod sursa(job #2474808)

Utilizator iulianrotaruRotaru Gheorghe-Iulian iulianrotaru Data 15 octombrie 2019 20:46:54
Problema Zone Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.92 kb
#include<fstream>
#include<algorithm>
#define ll long long
using namespace std;
ifstream f("zone.in"); ofstream g("zone.out");
int n,i,j,l1,l2,c1,c2,ok,a;
ll sum,v[10],r[10],s[513][513];
ll suma(int x1, int y1, int x2, int y2)
{   return s[x2][y2]+s[x1][y1]-s[x2][y1]-s[x1][y2];}
void caut()
{   int st=1,dr=9;
    while(st<=dr)
    {   int mij=(st+dr)>>1;
        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; caut();
            if(ok)
            {   for(l2=l1+1; l2<n-1;  l2++)
                {   sum=suma(l1,0,l2,c1); ok=0; caut();
                    if(ok)
                    {   for(c2=c1+1; c2<n-1; c2++)
                        {   sum=suma(0,c1,l1,c2);  ok=0; caut();
                            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;}
                            }
                        }
                    }
                }
            }
        }
    }
}