Cod sursa(job #2640902)

Utilizator stefan.popescuPopescu Stefan stefan.popescu Data 8 august 2020 23:17:23
Problema Balans Scor 25
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.89 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 maxi, width, rezmax;
long long a[302][302], vec[302], vec2[302];
deque <short> q;
inline void baga(short poz){
    while(!q.empty()&&vec2[q.back()]>=vec2[poz])
        q.pop_back();
    q.push_back(poz);
}
inline void scoate(short poz){
    if(q.front()==poz) q.pop_front();
}
inline long long getSum(short x1, short y1, short x2, short y2){
    return a[x2][y2]-a[x2][y1-1]-a[x1-1][y2]+a[x1-1][y1-1];
}
bool check(long long target){
    q.clear();
    long long sumMax=-1;
    for(int i=1; i<=2*m; i++){
        vec2[i]=vec[i]-target+vec2[i-1];
        if(i-m>=0) scoate(i-m);
        if(i-cMin>=0){
            baga(i-cMin);
            sumMax=max(sumMax, vec2[i]-vec2[q.front()]);
        }
    }
    return sumMax>=0;
}
void twoPointer(short x1, short x2){
    width=x2-x1+1; maxi=0;
    for(int i=1; i<=2*m; i++)
        vec[i]=getSum(x1, i, x2, i), maxi=max(maxi, vec[i]);
    long long st=0, dr=maxi, 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/width);
}
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]+a[i][j-1]-a[i-1][j-1];

    //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;
}