Cod sursa(job #803992)

Utilizator veleanduAlex Velea veleandu Data 28 octombrie 2012 17:55:25
Problema Balans Scor 35
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.51 kb
#include <cstdio>
#include <iostream>
using namespace std;

    #define prec (1<<18)
    #define max_n 305
    #define calc(x) (Sp[j][x]-Sp[i-1][x])
    int n,m,r,c;
    int i,j;
    long long El[max_n][max_n];
    long long Sp[max_n][max_n];
    int Deq[2*max_n];

bool solve ( long long Me ){
    int i,j,k;
    for ( i=1; i<=n; i++ ){
        for ( j=1; j<=m; j++ ){
            Sp[i][j]= (long long) Sp[i-1][j] + Sp[i][j-1] - Sp[i-1][j-1] +El[i][j] - Me;
        }
    }
    long long act,first,last;
    for ( i=1; i<=n/2; i++ ){
        for ( j=i+r-1; ( j<i+n/2-1); j++ ){
            act=0;
            first=last=0;
            // initializam "suma"
            Deq[0]=0;
            for ( k=c; k<=m; k++ ){
                // adaugam coloana actuala.
                act=calc(k);
                if ( act - calc(Deq[first] )>= 0 ){
                    return 1;
                }
                // scoatem din Deq.
                while ( ( last>=first ) && ( calc(k-c+1) < calc ( Deq[last] ) ) )
                    last--;
                Deq[++last]=k-c+1;
                if ( Deq[first] == k-(m/2)+1 )
                    first++;
            }
        }
    }
    return 0;
}

 float CB (){    
    long long rez=0,ind=(long long)(1<<20)*prec;
    for ( ; ind; ind>>=1 ){
        if ( solve ( rez+ind ) ){
            rez+=ind;
        }
    }
    return (float)(1.0*rez/prec);
}

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

    scanf ("%d %d %d %d", &n, &m, &r, &c );
    for ( i=1; i<=n; i++ ){
        for ( j=1; j<=m; j++ ){
            scanf ("%lld", &El[i][j] );
//            El[i][j]*=prec;
            El[ i+n ][ j ]=El[ i ][ j ];
            El[ i ][ j+m ]=El[ i ][ j ];
            El[ i+n ][ j+m ]=El[ i ][ j ];
        }
    }
    n*=2;
    m*=2;
    long long maxim=0;
    for ( i=1; i<=n; i++ ){
        for ( j=1; j<=m; j++ ){
            Sp[i][j]= Sp[i-1][j]+Sp[i][j-1]-Sp[i-1][j-1]+El[i][j];
        }
    }
    int i,j,k,l;
    for ( i=1; i<=n/2; i++ )
        for ( j=i+r-1; j<i+n/2; j++ )
            for ( k=1; k<=m/2; k++ )
                for ( l=k+c-1; l<k+m/2; l++ )
                    if ( ( Sp[j][l]-Sp[j][k-1]-Sp[i-1][l] +Sp[i-1][k-1] )*1000/( (j-i+1) * (l-k+1))> maxim ) 
                    {
//                        printf("%d %d %d %d\n", i,j,k,l);
                        maxim= ( Sp[j][l]-Sp[j][k-1]-Sp[i-1][l] +Sp[i-1][k-1] )*1000 /( (j-i+1)*(l-k+1) );
                    }
    printf("%.3f",double(maxim/1000.0));
//    printf("%.3f", CB() );
    return 0;
}