Cod sursa(job #1780521)

Utilizator PopoviciRobertPopovici Robert PopoviciRobert Data 16 octombrie 2016 12:31:29
Problema Balans Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.6 kb
#include <cstdio>
#define MAXN 150
#define INF 1000000000
long long mat[2*MAXN+1][2*MAXN+1];
long long v[2*MAXN+1];
long long sp[2*MAXN+1];
int dq[2*MAXN+1];
inline char cauta(long long med,int m,int c,int l1,int l2){
   int i,b,e;
   long long max;
   b=0;
   e=-1;
   max=-INF;
   for(i=1;i<2*m;i++){
       sp[i]=sp[i-1]-med+mat[l2][i]-mat[l1][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,ans,rez,pas,max;
   char flag;
   fi=fopen("balans.in" ,"r");
   fout=fopen("balans.out" ,"w");
   fscanf(fi,"%d %d %d %d " ,&n,&m,&r,&c);
   max=0;
   for(i=1;i<=n;i++)
     for(j=1;j<=m;j++){
       fscanf(fi,"%d " ,&mat[i][j]);
       mat[i][j]*=1000;
       if(mat[i][j]>max)
         max=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;
   rez=0;
   pas=1;
   while(pas<=max)
     pas*=2;
   pas/=2;
   for(;pas;pas>>=1){
     flag=0;
     for(l1=0;l1<=2*n-r&&flag==0;l1++)
      for(l2=l1+r;l2<=2*n&&flag==0;l2++)
       if(l2-l1<=n){
          if(cauta(1LL*(rez+pas)*(l2-l1),m,c,l1,l2)==1){
             rez+=pas;
             ans=rez;
             flag=1;
          }
       }
   }
   fprintf(fout,"%d.%d" ,ans/1000,ans%1000);
   fclose(fi);
   fclose(fout);
   return 0;
}