Cod sursa(job #2347914)

Utilizator alexradu04Radu Alexandru alexradu04 Data 19 februarie 2019 11:15:22
Problema Balans Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.74 kb
#include <iostream>
#include <cstdio>
#include <deque>
#define MAXN 164
#define MAXM 164

using namespace std;

int a[2*MAXN][2*MAXM];
int pre[2*MAXN][2*MAXN];
deque<int>q;
double crt[2*MAXM];
int n, m, r, c;


int verif(int stx,int len,double k)
{
    for(int i=1; i<=2*m; i++)
        crt[i]=crt[i-1]+pre[stx+len-1][i]-pre[stx-1][i]-(k*len);
    if(crt[c]>=0)
        return 1;
    q.clear();
    for(int i=c+1; i<=2*m; i++)
    {
        while(!q.empty()&&crt[i-c]<=crt[q.back()])
            q.pop_back();
        q.push_back(i-c);
        while(q.size()>1&&i-q.front()+1>m)
            q.pop_front();
        double scad=crt[q.front()];
        if(crt[i]-scad>=0)
            return 1;
    }
    return 0;
}
int main()
{
    freopen("balans.in","r",stdin);
    freopen("balans.out","w",stdout);
    scanf("%d %d %d %d",&n,&m,&r,&c);
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
        {
            scanf("%d",&a[i][j]);
            a[i][j+m]=a[i+n][j]=a[i+n][j+m]=a[i][j];
        }
    for(int i=1; i<=2*n; i++)
        for(int j=1; j<=2*m; j++)
            pre[i][j]=pre[i-1][j]+a[i][j];
    int rez=0;
    for(int i=1; i<= n; i++)
        for(int j=r; j<=n; j++)
        {
            int ls=rez,ld=(1<<30),k;
            if(!verif(i,j,ls/1000.0))
                continue;
            for(int it=1; it<=30&&ls<ld; it++)
            {
                k=(ls+ld)/2;
                if(verif(i,j,k/1000.0))
                    ls=k;
                else
                    ld=k-1;
            }
            for(; verif(i,j,ls/1000.0); ++ls);
            if(!verif(i,j,ls/1000.0))
                --ls;
            rez=max(rez,ls);
        }
    printf("%.3f",rez/1000.0);

    return 0;
}