Cod sursa(job #2350889)

Utilizator Cojocaru_Andrei_CristianCojocaru Andrei Cristian Cojocaru_Andrei_Cristian Data 21 februarie 2019 19:35:30
Problema Balans Scor 35
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.66 kb
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 150;
int n, m, r, c;
int mat[MAXN + 5][MAXN + 5];
long long v[2 * MAXN + 5], sp[2 * MAXN + 5];
int mod(int a)
{
    if(a!=n)
        a=a%n;
    return a;
}
bool verif(int val)
{
    for(int i=1; i+r-1<=2*n; i++)
    {
        for(int j=1; j<=2*m; j++)
            v[j]=0;
        for(int j=i; j<i+r-1; j++)
            for(int k=1; k<=m; k++)
                v[k]=v[k+m]=v[k]+mat[mod(j)][k]-val;
        for(int j=i+r-1; j<=min(2*n,i+n-1); ++j)
        {
            for(int k=1; k<=m; k++)
                v[k]=v[k+m]=v[k]+mat[mod(j)][k]-val;
            for (int k=1;k<c;k++)
                sp[k]=sp[k-1]+v[k];
            deque<int>dq;
            for(int k=c;k<2*m;k++)
            {
                sp[k]=sp[k-1]+v[k];
                while(!dq.empty()&&sp[dq.back()]>=sp[k-c])
                    dq.pop_back();
                dq.push_back(k-c);
                if (sp[k]-sp[dq.front()]>= 0)
                    return 1;
                if (dq.front()==k-m)
                    dq.pop_front();
            }
        }
    }
    return 0;
}

int main()
{
    freopen("balans.in","r",stdin);
    ofstream cout("balans.out");
    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",&mat[i][j]);
            mat[i][j]=mat[i][j]*1000;
        }
    int st=0,dr=100000005,last=0;
    while(st<=dr)
    {
        int mij=(st+dr)/2;
        if(verif(mij))
            last=mij,st=mij+1;
        else
            dr=mij-1;
    }
    cout<<fixed<<setprecision(3)<<(double)last/1000;
    return 0;
}