Cod sursa(job #1780496)

Utilizator PopoviciRobertPopovici Robert PopoviciRobert Data 16 octombrie 2016 12:11:06
Problema Balans Scor 15
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.47 kb
#include <cstdio>
#define MAXN 150
#define INF 1000000000
const double EPS=0.001;
int mat[2*MAXN+1][2*MAXN+1];
int v[2*MAXN+1];
double sp[2*MAXN+1];
int dq[2*MAXN+1];
inline char cauta(double med,int m,int c){
   int i,b,e;
   double max;
   for(i=1;i<=2*m;i++)
      sp[i]=sp[i-1]+v[i]-med;
   b=0;
   e=-1;
   max=-INF;
   for(i=1;i<=2*m;i++){
       if(e>=b&&dq[b]<i-m)
          b++;
       if(i-c>=0){
          while(e>=b&&sp[i-c]<=sp[dq[e]])
             e--;
          dq[++e]=i-c;
          if(sp[i]-sp[dq[b]]>max)
            max=sp[i]-sp[dq[b]];
       }
   }
   if(max>=0)
     return 1;
   return 0;
}
int main(){
   FILE*fi,*fout;
   int i,j,n,m,r,c,l1,l2;
   double ans,rez,pas;
   fi=fopen("balans.in" ,"r");
   fout=fopen("balans.out" ,"w");
   fscanf(fi,"%d %d %d %d " ,&n,&m,&r,&c);
   for(i=1;i<=n;i++)
     for(j=1;j<=m;j++){
       fscanf(fi,"%d " ,&mat[i][j]);
       mat[i+n][j]=mat[i][j];
       mat[i][j+m]=mat[i][j];
       mat[i+n][j+m]=mat[i][j];
     }
   for(i=1;i<=2*n;i++)
    for(j=1;j<=2*m;j++)
      mat[i][j]+=mat[i-1][j];
   ans=0;
   for(l1=0;l1<=2*n-r;l1++)
    for(l2=l1+r;l2<=2*n;l2++)
     if(l2-l1<=n){
        for(j=1;j<=2*m;j++)
           v[j]=mat[l2][j]-mat[l1][j];
        rez=0;
        pas=1;
        for(i=1;i<=16;i++)
           pas*=2;
        for(;pas>=EPS;pas/=2)
         if(cauta((rez+pas)*(l2-l1),m,c)==1)
           rez+=pas;
        if(ans<rez)
          ans=rez;
     }
   fprintf(fout,"%.3lf" ,ans);
   fclose(fi);
   fclose(fout);
   return 0;
}