Cod sursa(job #2711717)

Utilizator Alex_tz307Lorintz Alexandru Alex_tz307 Data 24 februarie 2021 17:03:28
Problema Balans Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.66 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("balans.in");
ofstream fout("balans.out");

const int NMAX = 303;
int N, M, R, C, a[NMAX][NMAX], dp[NMAX][NMAX], sum[NMAX];

bool check(const int &x) {
    for(int i = 1; i <= (N << 1); ++i)
        for(int j = 1; j <= (M << 1); ++j)
            dp[i][j] = dp[i - 1][j] + (a[i][j] - x);
    for(int l1 = 1; l1 <= N; ++l1)
        for(int l2 = l1 + R - 1; l2 <= (N << 1) && l2 < l1 + N; ++l2) {
            deque<int> Q;
            for(int j = 1; j <= (M << 1); ++j) {
                sum[j] = sum[j - 1] + (dp[l2][j] - dp[l1 - 1][j]);
                if(j >= C) {
                    while(!Q.empty() && Q.front() <= j - M)
                        Q.pop_front();
                    while(!Q.empty() && sum[j - C] <= sum[Q.back()])
                        Q.pop_back();
                    Q.push_back(j - C);
                    if(sum[j] - sum[Q.front()] >= 0)
                        return true;
                }
            }
        }
    return false;
}

int main() {
    fin >> N >> M >> R >> C;
    for(int i = 1; i <= N; ++i)
        for(int j = 1; j <= M; ++j) {
            fin >> a[i][j];
            a[i][j] *= 1000;
            a[i + N][j] = a[i][j + M] = a[i + N][j + M] = a[i][j];
        }
    int st = 1, dr = 1e8, ans = 0;
    while(st <= dr) {
        int mid = (st + dr) >> 1;
        if(check(mid)) {
            ans = mid;
            st = mid + 1;
        }
        else
            dr = mid - 1;
    }
    fout << ans / 1000 << '.';
    ans %= 1000;
    if(ans < 100)
        fout << '0';
    if(ans < 10)
        fout << '0';
    fout << ans << '\n';
}