Cod sursa(job #857380)

Utilizator DaNutZ2UuUUBB Bora Dan DaNutZ2UuU Data 17 ianuarie 2013 19:35:22
Problema Zone Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.83 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);
              /*r10 = suma 0, 0, l2, c3*/ 
              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;}