Cod sursa(job #396507)

Utilizator DraStiKDragos Oprica DraStiK Data 15 februarie 2010 14:57:22
Problema Balans Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.24 kb
#include <algorithm>
using namespace std;

#define DIM 305

int a[DIM][DIM],sum[DIM][DIM];
int n,m,r,c;
double nrt;

void read ()
{
    int i,j;

    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+n][j]=a[i][j+m]=a[i+n][j+m]=a[i][j];
        }
}

void init ()
{
    int i,j;

    for (i=1; i<=(n<<1); ++i)
        for (j=1; j<=(m<<1); ++j)
            sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+a[i][j];
}

void solve ()
{
    int rr,cc,i,j,maxim;

    for (rr=r; rr<=n; ++rr)
        for (cc=c; cc<=m; ++cc)
        {
            maxim=0;
            for (i=rr+1; i<=(n<<1); ++i)
                for (j=cc+1; j<=(m<<1); ++j)
                    if (sum[i][j]-sum[i-rr][j]-sum[i][j-cc]+sum[i-rr][j-cc]>maxim)
                        maxim=sum[i][j]-sum[i-rr][j]-sum[i][j-cc]+sum[i-rr][j-cc];
            if ((double)maxim/(rr*cc)>nrt)
                nrt=(double)maxim/(rr*cc);
        }
    nrt*=1000; nrt=(int)nrt; nrt/=1000;
    printf ("%.3lf",nrt);
}

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

    read ();
    init ();
    solve ();

    return 0;
}