Cod sursa(job #2333384)

Utilizator triscacezarTrisca Vicol Cezar triscacezar Data 31 ianuarie 2019 23:09:04
Problema Balans Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.6 kb
#include <bits/stdc++.h>

using namespace std;

ifstream f("balans.in");
ofstream g("balans.out");

int i,j,k,n,m,r,c;
long long lo,hi,s_part[310],a[310][310];
deque<int> coada;

bool hmm(long long x)
{
    for(i=1;i<=2*n;i++)
    {
        for(k=1;k<=2*m;k++)
            s_part[k]=0;
        for(j=i;j<=2*n&&j<=i+n-1;j++)
        {
            long long sum=0;
            for(k=1;k<=2*m;k++)
            {
                sum+=a[j][k]-x;
                s_part[k]+=sum;
            }
            if(j<i+r-1)
                continue;
            coada.clear();
            for(k=1;k<=2*m;k++)
            {
                while(!coada.empty()&&coada.front()<k-m)
                    coada.pop_front();
                if(k>=c)
                {
                    while(!coada.empty()&&s_part[coada.back()]>=s_part[k-c])
                        coada.pop_back();
                    coada.push_back(k-c);
                    if(s_part[coada.front()]<=s_part[k])
                        return true;
                }
            }
        }
    }
    return false;
}

int main()
{
    f>>n>>m>>r>>c;
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
        {
            f>>a[i][j];
            a[i][j]*=1000;
            a[i][j+m]=a[i][j];
        }
    for(i=n+1;i<=2*n;i++)
        for(j=1;j<=2*m;j++)
            a[i][j]=a[i-n][j];
    lo=0,hi=1e9;
    while(lo<hi)
    {
        long long mi=(lo+hi)/2;
        if(hmm(mi))
            lo=mi+1;
        else
            hi=mi;
    }
    g<<fixed<<setprecision(3)<<(long double)(lo-1)/1000.0;
    return 0;
}