Cod sursa(job #2641077)

Utilizator stefan.popescuPopescu Stefan stefan.popescu Data 9 august 2020 21:14:17
Problema Balans Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.7 kb
#include <iostream>
#include <fstream>
#include <iomanip>
#include <deque>
using namespace std;
ifstream in ("balans.in");
ofstream out("balans.out");
int n, m, lMin, cMin;
long long width, rezmax;
long long a[302][302], vec[302], vec2[302];
deque <short> q;
inline void scoate(short poz){
    if(q.front()==poz) q.pop_front();
}
bool check(long long target){
    q.clear();
    for(int i=1; i<=2*m; i++)
        vec2[i]=vec[i]-target*width+vec2[i-1];

    if(vec2[cMin]>=0) return true;

    for(int i=cMin+1; i<=2*m; i++){

        while(!q.empty()&&vec2[q.back()]>=vec2[i-cMin])
            q.pop_back();
        q.push_back(i-cMin);

        while(i-q.front()+1>m)
            q.pop_front();

        if(vec2[i]-vec2[q.front()]>=0) return true;
    }
    return false;
}
void twoPointer(short x1, short x2){
    width=x2-x1+1;
    for(int i=1; i<=2*m; i++)
        vec[i]=a[x2][i]-a[x1-1][i];
    long long st=0, dr=(1<<30), ans=0;

    while(st<=dr){
        long long mij=(st+dr)/2;
        if(check(mij)){
            ans=mij;
            st=mij+1;
        }
        else
            dr=mij-1;
    }
    rezmax=max(rezmax, ans);
}
int main()
{
    in>>n>>m>>lMin>>cMin;
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
        {
           in>>a[i][j];
           a[i][j]*=1000;
           a[n+i][j]=a[i][m+i]=a[n+i][m+j]=a[i][j];
        }
    for(int i=1; i<=2*n; i++)
        for(int j=1; j<=2*m; j++)
            a[i][j]+=a[i-1][j];

    //twoPointer(3, 4);
    for(int i=1; i<=2*n-lMin+1; i++)
        for(int j=i+lMin-1; j-i+1<=n&&j<=2*n; j++)
            twoPointer(i, j);
    out<<fixed<<setprecision(3)<<(long double)rezmax/1000;
    return 0;
}