Cod sursa(job #3329626)

Utilizator Radu_BicliBiclineru Radu Radu_Bicli Data 14 decembrie 2025 17:57:22
Problema Balans Scor 15
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.07 kb
#include <bits/stdc++.h>

using namespace std;

#define USE_STD_IO 0
//#define if(USE_STD_IO) cout
#if USE_STD_IO
    #define fin cin
    #define fout cout
#else
    ifstream fin("balans.in");
    ofstream fout("balans.out");
#endif // USE_STD_IO

int n, m, r, c, i, ii, j, a[152][152], rasp;
double vv[2 * 152];
deque<int> q;

static inline bool Verif(double rap) {
    for(int j = 1; j <= 2 * m; j++) {
        vv[j] = vv[j - 1] + (a[ii][j] - a[i - 1][j]) - (ii - i + 1) * rap;
    }
    if(vv[c] >= 0) return true;

    q.clear();
    for(int j = c + 1; j <= 2 * m; j++) {
        while(!q.empty() && vv[j - c] <= vv[q.back()]) q.pop_back();
        q.push_back(j - c);

        while(!q.empty() && j - q.front() + 1 > m) q.pop_front();
        if(vv[j] >= vv[q.front()]) return true;
    }

    return false;
}

int main() {
    if(USE_STD_IO) ios_base::sync_with_stdio(false);
    fin.tie(nullptr);
    fout.tie(nullptr);

    fin >> n >> m >> r >> c;
    for(i = 1; i <= n; i++) {
        for(j = 1; j <= m; j++) {
            fin >> 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++) {
            a[i][j] += a[i - 1][j];
        }
    }

    for(i = 1; i <= n; i++) {
        for(ii = i + r - 1; ii <= i + n - 1; ii++) {
            int st = rasp, dr = 2e9;
            int sel = st;
            if(!Verif(st / 1000.0)) continue;

            int pas = 30;
            while(st <= dr && pas > 0) {
                int mij = st + (dr - st) / 2;
                if(Verif(mij / 1000.0)) {
                    sel = mij;
                    st = mij + 1;
                }
                else dr = mij - 1;
                pas--;
            }

            while(Verif(sel / 1000.0)) sel++;
            if(!Verif(sel / 1000.0)) sel--;
            rasp = max(rasp, sel);
        }
    }
    fout << setprecision(3) << fixed;
    fout << rasp / 1000.0;

    return 0;
}