Cod sursa(job #801771)

Utilizator wzrdwzrd tst wzrd Data 24 octombrie 2012 22:01:48
Problema Balans Scor 25
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.12 kb
#include <iostream>
#include <iomanip>
#include <fstream>
#define DN 305
using namespace std;

int n,m,r,c,mc[DN][DN],sc[DN][DN],N,M,dq[DN],st,dr;
double v[DN];

bool check(double x) {
    for(int i1=1; i1<=N; ++i1) for(int i2=i1+r-1; i2<=n; ++i2) {
        for(int i=1; i<=m; ++i) v[i]=sc[i2][i]-sc[i1-1][i]-x*(i2-i1+1)+v[i-1];
        if(v[c]>=0) return 1;
        st=0,dr=-1;
        for(int i=c+1; i<=m; ++i) {
            for(;st<=dr && v[dq[dr]]>=v[i-c]; --dr);
            dq[++dr]=i-c;
            for(;i-dq[st]+1>M; ++st);
            if(v[i]-v[dq[st]]>=0) return 1;
        }
    }
    return 0;
}

int main()
{
    ifstream f("balans.in");
    ofstream g("balans.out");
    f>>n>>m>>r>>c;
    N=n; M=m;
    for(int i=1; i<=n; ++i) for(int j=1; j<=m; ++j) {
        f>>mc[i][j];
        mc[i+n][j]=mc[i][j+m]=mc[i+n][j+m]=mc[i][j];
    }
    n<<=1; m<<=1;
    for(int i=1; i<=n; ++i) for(int j=1; j<=m; ++j) sc[i][j]=sc[i-1][j]+mc[i][j];
    double ls=1,ld=10000000000,m;
    for(int i=1; i<=64; ++i) {
        m=(ls+ld)*0.5;
        if(check(m)) ls=m;
        else ld=m;
    }
    g<<fixed<<setprecision(3)<<ls;
    return 0;
}