Cod sursa(job #2333166)

Utilizator Andrei_CotorAndrei Cotor Andrei_Cotor Data 31 ianuarie 2019 19:04:18
Problema Balans Scor 25
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.66 kb
#include<stdio.h>
#include<queue>
using namespace std;
FILE *fi=fopen("balans.in","r");
FILE *fo=fopen("balans.out","w");
int n,m,i,j,k,rez,aux,r,c,A[305][305],Sum[305],S[305],Med[305],Min[305];
long long Aux[305];
deque<int> Q;

bool check(int x)
{
    int i;
    Q.clear();
    for(i=1; i<=2*m; i++)
    {
        Aux[i]=Aux[i-1]+1LL*Med[i]-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();
    }
    for(i=c+1; i<=2*m; i++)
        if(Aux[i]-Aux[Min[i-c]]>=0)
            return 1;
    return 0;
}

int main()
{
    fscanf(fi,"%d%d%d%d",&n,&m,&r,&c);
    for(i=1; i<=n; i++)
        for(j=1; j<=m; j++)
        {
            fscanf(fi,"%d",&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--)
        {
            for(k=1; k<=2*m; k++)
                Med[k]=(1LL*S[k]*1000)/(i-j+1);
            aux=0;
            for(k=26; k>=0; k--)
                if(check(aux+(1<<k)))
                    aux=aux+(1<<k);
            rez=max(rez,aux);
            for(k=1; k<=2*m; k++)
                S[k]+=A[j-1][k];
        }
    }
    fprintf(fo,"%.3f\n",1.0*rez/1000);
    fclose(fi);
    fclose(fo);
    return 0;
}