Cod sursa(job #186498)

Utilizator stef2nStefan Istrate stef2n Data 28 aprilie 2008 01:44:01
Problema Balans Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.67 kb
#include <fstream>
#include <iomanip>
#include <cmath>
#include <cassert>
using namespace std;

const int MAX_D = 151;
const int MAX_AVG = 100000000;
const long long INF = 1LL << 50;

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

int M, N, R, C, oldR;
long long A[MAX_D << 1][MAX_D << 1];
long long S[MAX_D << 1], T[MAX_D << 1];

void read() {
    in >> M >> N >> R >> C;
    for(int i = 1; i <= M; ++i)
        for(int j = 1; j <= N; ++j) {
            in >> A[i][j];
            A[i + M][j] = A[i][j + N] = A[i + M][j + N] = A[i][j] *= 1000;
        }
    for(int i = 1; i <= 2 * M; ++i)
        for(int j = 1; j <= 2 * N; ++j)
            A[i][j] += A[i - 1][j];
}

long long max_sum(long long X) {
    for(int i = 1; i <= 2 * N; ++i)
        T[i] = T[i - 1] + S[i] - X;
    long long sum = -INF, t = INF;
    for(int i = C; i <= 2 * N; ++i) {
        t = min(t, T[i - C]);
        sum = max(sum, T[i] - t);
    }
    return sum;
}

bool solve(long long X) {
    for(R = oldR; R <= M; ++R)
        for(int i = 1; i <= M; ++i) {
            for(int j = 1; j <= 2 * N; ++j)
                S[j] = A[i + R - 1][j] - A[i - 1][j];
            if(max_sum(R * X) >= 0)
                return true;
        }
    return false;
}

int binary_search(const int &lo, const int &hi) {
    if(lo == hi)
        return lo;
    if(!solve((lo + hi) / 2 + 1))
        return binary_search(lo, (lo + hi) / 2);
    else
        return binary_search((lo + hi) / 2 + 1, hi);
}


int main() {
    read();
    assert(R == M || C == N);
    if(!R) ++R;
    if(!C) ++C;
    oldR = R;
    int X = binary_search(0, MAX_AVG);
    out << X / 1000 << "." << (X % 1000) / 100 << (X % 100) / 10 << X % 10 << "\n";
    return 0;
}