Cod sursa(job #779318)

Utilizator ionut_blesneagIonut Blesneag ionut_blesneag Data 17 august 2012 14:51:12
Problema Zone Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2 kb
#include<fstream>
#include<algorithm>
using namespace std;

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

int n,i,j,c;
long long v[10], sum;
int a[513][513];
long long s[513][513],r[10];
int l1,l2,c1,c2,mij,gasit;

long long suma(int x1, int y1, int x2, int y2)
{long long sm=0;
 sm=s[x2][y2]+s[x1][y1]-s[x2][y1]-s[x1][y2];
 return sm;
}  


void cautare(int left, int right)
{ while(left<=right)
   {mij=(left+right)/2;
    if(v[mij]==sum)
       {gasit=1;
        return;}
    if(v[mij]>sum)
       right=mij-1;
    else
       left=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[i][j];
    s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j];}
/*for(i=1; i<=n; i++)
 {for(j=1; j<=n; j++)
   g<<s[i][j]<<" ";
  g<<endl;}   */
    
f.close();
l1=1;   
while(l1<n-1)
{
for(c1=1; c1<n-1; c1++)
  {sum=suma(0,0,l1,c1);
   gasit=0;
   cautare(1,9);
   if(gasit==1)
     {for(l2=l1+1; l2<n-1;  l2++)
        {sum=suma(l1,0,l2,c1);
         gasit=0;
         cautare(1,9);
         if(gasit==1)  
          { for(c2=c1+1; c2<n-1; c2++)
           {sum=suma(0,c1,l1,c2);  
            gasit=0;
            cautare(1,9);
            if(gasit==1)
             {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);
              
              gasit=0;
              sort(r+1,r+10);
              for(i=1; i<=9; i++)
                if(r[i]!=v[i])
                  gasit=1;
              if(gasit==0)   
                 {g<<l1<<" "<<l2<<" "<<c1<<" "<<c2;
                  g.close();
                  return 0;}  
              }
           }}  
      }}    
   
   }
l1++;             
}

  
g.close();
return 0;}