Cod sursa(job #58440)

Utilizator crawlerPuni Andrei Paul crawler Data 5 mai 2007 21:15:47
Problema Balans Scor 75
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.91 kb
#include <cstdio>

using namespace std;

int v[612][612], s[612][612];

int main()
 {
  freopen("balans.in","r",stdin);
  freopen("balans.out","w",stdout);

  int n,m,r,c,i,j, tmp, C, prod;
  double max = -1, aux;

  scanf("%d%d%d%d",&n,&m,&r,&c);C = c;

  for(i=1;i<=n;++i)
   for(j=1;j<=m;++j)
    {
     scanf("%d",v[i]+j);
     v[i+n][j] = v[i][j];
     v[i][j+m] = v[i][j];
     v[i+n][j+m] = v[i][j];
    }

  n<<=1;
  m<<=1;

  for(i=1;i<=n;++i)
   for(j=1;j<=m;++j)
    s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + v[i][j];

  int N = n/2, M = m/2;

  for(;r<=N;++r)
   for(c=C;c<=M;++c)
    {
     prod = r*c;
     for(i=r;i<=n;++i)
      for(j=c;j<=m;++j)
       {
        tmp = s[i][j] - s[i-r][j] - s[i][j-c] + s[i-r][j-c];
        aux = tmp;
        if(aux > max*prod)
         max = aux/prod;
       }
    }

  printf("%.3f\n", max - 0.000499);

  return 0;
 }