Cod sursa(job #2350871)

Utilizator Cojocaru_Andrei_CristianCojocaru Andrei Cristian Cojocaru_Andrei_Cristian Data 21 februarie 2019 19:29:19
Problema Balans Scor 40
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.64 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()
{
    ifstream cin("balans.in");
    ofstream cout("balans.out");
    cin>>n>>m>>r>>c;
    for (int i=1; i<=n; i++)
        for (int j=1; j<=m; j++)
        {
            cin>>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;
}