Cod sursa(job #256880)

Utilizator MariusMarius Stroe Marius Data 12 februarie 2009 12:53:48
Problema Balans Scor 95
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.93 kb
#include <fstream>
#include <iostream>
using namespace std;

const char iname[] = "balans.in";
const char oname[] = "balans.out";

#define FOR(i, a, b)  for (int i = (a); i <= (b); ++ i)

typedef long long i64;

const int MAXN = 300;

int A[MAXN][MAXN], rows, cols, r, c, irows, icols;

i64 S[MAXN][MAXN];


void read_in(void) {
    ifstream in(iname);
    in >> rows >> cols >> r >> c;
    FOR (i, 1, rows) FOR (j, 1, cols) {
        in >> A[i][j];
        A[i][j] *= 1000;
        if (i < rows)
            A[i + rows][j] = A[i][j];
        if (j < cols)
            A[i][j + cols] = A[i][j];
        if (i < rows && j < cols)
            A[i + rows][j + cols] = A[i][j];
    }
    irows = rows, icols = cols;
    rows = 2 * rows - 1, cols = 2 * cols - 1;
    in.close();
}

bool work(const int blns) {
    int deque[MAXN], *head, *tail;
    i64 T[MAXN] = {0}, ret = -1000000000000LL;

    FOR (i, 1, rows) FOR (j, 1, cols)
        S[i][j] = S[i - 1][j] + (i64)(A[i][j] - blns);

    FOR (i, 1, irows) FOR (k, i + r - 1, i + irows - 1) {
        FOR (j, 1, cols)
            T[j] = T[j - 1] + S[k][j] - S[i - 1][j];
        head = tail = deque;
        *head = 0;
        FOR (j, c, cols) {
            while (head <= tail && *head < j - icols)
                head ++;
            if (ret < T[j] - T[*head])
                ret = T[j] - T[*head];
            while (head <= tail && T[j - c + 1] <= T[*tail])
                tail --;
            tail ++, *tail = j - c + 1;
        }
    }
    return ret >= 0;
}

int main(void)
{
    read_in();
    const int upper_limit = 100000000;      // 1e8
    int i, delta = 1 << 26;
    for (i = 0; delta; delta /= 2)
        if ((i + delta <= upper_limit) && work(i + delta))
            i += delta;

    ofstream out(oname);
    out << i / 1000 << ".";
    i %= 1000;
    out << i / 100 << (i % 100) / 10 << i % 10;
    out.close();
    return 0;
}