Cod sursa(job #217594)

Utilizator VmanDuta Vlad Vman Data 29 octombrie 2008 01:20:46
Problema Balans Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.78 kb
#include <cstdio>

#define Nmax 303
#define Mmax 303

int N, M, R, C, Amax;
int A[Nmax][Mmax];
int S[Nmax][Mmax];
int i,j;

void citire()
{
 freopen("balans.in","r",stdin);
 scanf("%d %d %d %d",&N,&M,&R,&C);
 for (i=1; i<=N; ++i)
     for (j=1; j<=M; ++j)
        {
         scanf("%d", &A[i][j]);
         A[i][j] *= 1000;
         A[i][M+j] = A[i+N][j] = A[i+N][j+M] = A[i][j];
         Amax = Amax > A[i][j] ? Amax : A[i][j];
        }
}

void compute()
{
 for (i=1; i<=2*N; ++i)
     for (j=1; j<=2*M; ++j)
         S[i][j] = S[i-1][j] + A[i][j];
}

int exista(int V)
{
 int st,dr,k,dif,T;
 for (i=0; i<2*N; ++i)     
     for (j=i+R; j<=2*N && j<=i+N; ++j)
         {
          st=1;
          dr=C;
          dif = V*(j-i);
          for (k=1, T=0; k<=C; ++k)
              T += S[j][k] - S[i][k] - dif;
          if (T>=0) return 1;
          while (dr<2*N)
                {
                 ++dr;
                 T += S[j][dr] - S[i][dr] - dif;
                 while (dr-st>=N)
                        {
                         T -= S[j][st] - S[i][st] - dif;
                         ++st;
                        }
                 while (T - S[j][st] + S[i][st] + dif > T && dr-st>=C)
                       {
                        T -= S[j][st] - S[i][st] - dif;
                        ++st;
                       }
                 if (T>=0) return 1;
                }
         }
 return 0;
}

void cauta()
{
 int p=1, nr=0;
 while ((p << 1)<=Amax) p<<=1;
 while (p)
       {
        if (exista(nr+p)) nr+=p;
        p>>=1;
        while (nr+p>Amax) p>>=1;
       }
 printf("%d.%d\n",nr/1000,nr%1000);
}

int main()
{
 citire();
 compute();
 freopen("balans.out","w",stdout);
 cauta();
 fclose(stdout);
 return 0;
}