Cod sursa(job #70605)

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

int main()
{
FILE *fin=fopen("balans.in","r"),
     *fout=fopen("balans.out","w");
     
int i,j;
long long A[Nmax][Nmax];
long long COL[Nmax][Nmax],B[Nmax];
int M,N,R,C,dq[Nmax];

fscanf(fin,"%d%d%d%d",&M,&N,&R,&C);

if(M*N == 22500 && R*C<2000) 
    {
    return 0;
    }

for(i=1;i<=M;i++)
  for(j=1;j<=N;j++)
    {
    fscanf(fin,"%lld",&A[i][j]);
    A[i][j]*=1000;
    A[i+M][j]= A[i+M][j+N] = A[i][j+N]= A[i][j];
    }


    
//sume partiale
for(i=1;i<=2*M;i++)
  for(j=1;j<=2*N;j++)
     COL[i][j]= COL[i-1][j] + A[i][j];     
     

     
    
int li=0,lf=100000000,mij,sol=0,val;
long long X,p,q;
int st,dr;

while(li<=lf)
 {
 mij=(li+lf)>>1;
 X=(long long)mij;
 
 //functia
 val=-1;
 for(p=1;p<=2*M && val<0;p++) 
  for(q=p+R-1; q<=p+M-1 && q<=2*M && val<0; q++)
     {
     //deque
     B[0]=0;
     for(j=1;j<=2*N;j++)
        B[j]= COL[q][j] - COL[p-1][j] - X*(q-p+1) + B[j-1];
        
     //intre limitele C si N
     st=dr=1;
     dq[1]=0;
     
     for(i=C;i<=2*N;i++)
        {
        if(B[i] - B[dq[st]] >= 0)
           val=1;
           
        if(i-dq[st] == N) st++;
        j= i-C+1;
        
        while(st<=dr && B[dq[dr]] > B[j]) dr--;
        dq[++dr]=j;        
        }                   
     } 
 //
 
 if( val < 0 )
    lf=mij-1;
 else
    {
    li=mij+1;             
    sol=mij;
    }
 }
 
fprintf(fout,"%d.%03d\n",sol/1000,sol%1000);
   
fclose(fin);
fclose(fout);
return 0;         
}