Cod sursa(job #2333161)

Utilizator Andrei_CotorAndrei Cotor Andrei_Cotor Data 31 ianuarie 2019 18:58:11
Problema Balans Scor 15
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.57 kb
#include<fstream>
#include<iomanip>
#include<queue>
using namespace std;
ifstream fi("balans.in");
ofstream fo("balans.out");
int n,m,i,j,k,rez,aux,r,c,A[305][305],Sum[305],S[305],Min[305];
long long Aux[305];
deque<int> Q;

bool check(int x, int l1, int l2)
{
    int i;
    Q.clear();
    for(i=1; i<=2*m; i++)
    {
        Aux[i]=Aux[i-1]+1LL*(1LL*S[i]*1000)/(l1-l2+1)-1LL*x;
        if(i>=c && i<=m && Aux[i]>=0)
            return 1;
        if(!Q.empty() && i-Q.front()>(m-c))
            Q.pop_front();
        while(!Q.empty() && Aux[i]<=Aux[Q.back()])
            Q.pop_back();
        Q.push_back(i);
        Min[i]=Q.front();
        if(i>c && Aux[i]-Aux[Min[i-c]]>=0)
            return 1;
    }
    return 0;
}

int main()
{
    fi>>n>>m>>r>>c;
    for(i=1; i<=n; i++)
        for(j=1; j<=m; j++)
        {
            fi>>A[i][j];
            A[i+n][j]=A[i][j];
            A[i][j+m]=A[i][j];
            A[i+n][j+m]=A[i][j];
        }
    for(i=1; i<=2*n; i++)
    {
        for(j=1; j<=2*m; j++)
        {
            Sum[j]+=A[i][j];
            if(i>r)
                Sum[j]-=A[i-r][j];
            S[j]=Sum[j];
        }
        for(j=i-r+1; j>=max(1,j-n+1); j--)
        {
            aux=0;
            for(k=26; k>=0; k--)
                if(check(aux+(1<<k),i,j))
                    aux=aux+(1<<k);
            rez=max(rez,aux);
            for(k=1; k<=2*m; k++)
                S[k]+=A[j-1][k];
        }
    }
    fo<<setprecision(3)<<fixed<<(1.0*rez/1000)<<"\n";
    fi.close();
    fo.close();
    return 0;
}