Cod sursa(job #70369)

Utilizator moga_florianFlorian MOGA moga_florian Data 5 iulie 2007 18:15:42
Problema Balans Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.52 kb
#include<stdio.h>
#define Nmax 305

int A[Nmax][Nmax],COL[Nmax][Nmax],M,N,R,C;
int B[Nmax],dq[Nmax];

int calc(int X)
{
int i,j,p,q,li,lf,max=-1;
//sume partiale
for(j=1;j<=2*N;j++)
  {
  COL[0][j]=0;
  for(i=1;i<=2*M;i++)
      COL[i][j] = COL[i-1][j] + A[i][j] - X;  
  }  
  
//linii limita
for(p=1;p<=2*M;p++) 
  for(q=p+R-1; q<=p+M-1 && q<=2*M; q++)
     {
     //deque
     for(j=1;j<=2*N;j++)
        B[j]= COL[q][j] - COL[p-1][j];
        
     B[0]=0;
     for(j=1;j<=2*N;j++)
        B[j] = B[j-1] + B[j];
        
     //intre limitele C si N
     li=lf=1;
     dq[1]=0;
     
     for(i=C;i<=2*N;i++)
        {
        if(B[i] - B[dq[li]] > max)
           max= B[i] - B[dq[li]];
           
        if(i-dq[li]+1 == N) li++;
        j= i-C+1;
        
        while(li<=lf && B[dq[lf]] > B[j]) lf--;
        dq[++lf]=j;        
        }                   
     }
return max;
}


int main()
{
FILE *fin=fopen("balans.in","r"),
     *fout=fopen("balans.out","w");
     
int i,j;

fscanf(fin,"%d%d%d%d",&M,&N,&R,&C);
for(i=1;i<=M;i++)
  for(j=1;j<=N;j++)
    {
    fscanf(fin,"%d",&A[i][j]);
    A[i][j]*=1000;
    A[i+M][j]= A[i+M][j+N] = A[i][j+N]= A[i][j];
    }
    
int li=1,lf=100000000,mij,sol=0;

while(li<=lf)
 {
 mij=(li+lf)>>1;
 if( calc(mij) <= 0 )
    {
    sol=mij;
    lf=mij-1;           
    }
 else
    li=mij+1;             
 }
 
double x= (double) sol / 1000.0;
fprintf(fout,"%.3f\n",x);
   
fclose(fin);
fclose(fout);
return 0;         
}