Cod sursa(job #2448423)

Utilizator pasoi_stefanPasoi Stefan pasoi_stefan Data 16 august 2019 20:59:55
Problema Balans Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.64 kb
#include<fstream>
#include<iomanip>
using namespace std;
ifstream cin("balans.in");
ofstream cout("balans.out");

int n,m,r,c,fr,bk;
int a[305][305],b[305][305],d[305];
long long s[305][305];
int le,ri;

inline long long dim(int i,int j,int k){

    return s[j][k]-s[i-1][k];

}

long long maxsecv(int i,int j){

    long long q=-1e13;

    fr=1; bk=0;

    for(int k=c;k<2*m;k++){

        while(fr<=bk && dim(i,j,d[bk])>=dim(i,j,k-c)) --bk;
        d[++bk]=k-c;

        if(d[fr]==k-m-1) ++fr;

        q=max(q,dim(i,j,k)-dim(i,j,d[fr]));

    }

    return q;

}

long long ans(int x){

    for(int i=1;i<2*n;i++)
        for(int j=1;j<2*m;j++)
            b[i][j]=a[i][j]-x;

    for(int i=1;i<2*n;i++)
        for(int j=1;j<2*m;j++)
            s[i][j]=b[i][j]+s[i][j-1]+s[i-1][j]-s[i-1][j-1];

    long long q=-1e13;

    for(int i=1;i<=2*n-r;i++)
        for(int j=i+r-1;j<=min(2*n-1,i+n-1);j++)
            q=max(q,maxsecv(i,j));

    return q;

}

int main(){

    cin>>n>>m>>r>>c;

    if(!r) r=1;
    if(!c) c=1;

    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++){

            cin>>a[i][j];
            a[i][j]*=1000;

        }

    for(int i=n+1;i<2*n;i++)
        for(int j=1;j<=m;j++)
            a[i][j]=a[i-n][j];

    for(int i=1;i<2*n;i++)
        for(int j=m+1;j<2*m;j++)
            a[i][j]=a[i][j-m];

    le=0; ri=1e8;

    while(ri-le>1){

        int middle=(ri+le)/2;

        if(ans(middle)>=0) le=middle;
        else ri=middle;

    }

    if(ans(le)>=0) cout<<setprecision(3)<<fixed<<le/1000.0;
    else cout<<setprecision(3)<<fixed<<ri/1000.0;

}