Cod sursa(job #1497669)

Utilizator chiriacandrei25Chiriac Andrei chiriacandrei25 Data 7 octombrie 2015 08:58:20
Problema Balans Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.72 kb
#include <stdio.h>
#define Nmax 155*2
#define CT 1000
#define LL long long
#define INF 2147000000

using namespace std;

int Deq[Nmax];
int a[Nmax][Nmax]; LL Sc[Nmax][Nmax];
LL Sum[Nmax];
int N,M,R,C;

inline LL Maxim(LL x,LL y){ return x>y ? x:y; }
inline LL Minim(LL x,LL y){ return x<y ? x:y; }

int bun(LL X){
    int i,i2,j,p,u; LL mx,sum_ac;

    for(i=1; i<=N; ++i)
        for(i2=i+R-1; i2<=i+N-1; ++i2){

            for(j=1;j<=2*M;++j) Sum[j]=Sum[j-1] + Sc[i2][j]-Sc[i-1][j] -X*(i2-i+1);

            p=1; u=0; mx=Sum[C];
            Deq[1]=1;
            for(j=C+1; j<=2*M; ++j){
                while( p<=u && Deq[p]+M-1 < j )
                    p++;

                sum_ac=Sum[j]-Sum[j-C];
                while( u>=p && Sum[j]-Sum[Deq[u]-1] <= sum_ac )
                    u--;
                Deq[++u]=j-C+1;

                mx=Maxim(mx,Sum[j]-Sum[Deq[p]-1]);
                if( Deq[p]>M ) break;
            }
            if( mx >= 0 )
                return 1;
        }
    return 0;
}

int main(){
    int i,j, Max=0,l,r,m,rez;
    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("%d",&a[i][j]),a[i][j]*=CT;
            a[i+N][j]=a[i][j+M]=a[i+N][j+M]=a[i][j];

            Max=Maxim(a[i][j],Max);
        }
    for(i=1;i<=2*N;++i)
        for(j=1;j<=2*M;++j)
            Sc[i][j]=Sc[i-1][j]+(LL)(a[i][j]);

    for(l=0, r=Max; l<=r; ){
        m=l+(r-l)/2;
        if( bun(m) ){
            rez=m;
            l=m+1;
        }
        else r=m-1;
    }

    printf("%.3lf\n",(rez*1.0/CT));
    fclose(stdin); fclose(stdout);
    return 0;
}