Cod sursa(job #256858)

Utilizator MariusMarius Stroe Marius Data 12 februarie 2009 12:25:21
Problema Balans Scor 95
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.11 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)

const int MAXN = 300;

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

typedef long long i64;


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 S[MAXN], T[MAXN] = {0}, ret = -1000000000000LL;

    FOR (i, 1, irows) {
        FOR (j, 1, cols)   S[j] = 0;
        FOR (k, i, i + irows - 1) {
            FOR (j, 1, cols)  S[j] += (i64)(A[k][j] - blns);
            if (k - i + 1 >= r) {
                head = tail = deque;
                *head = 0;
                FOR (j, 1, cols) {
                    T[j] = T[j - 1] + S[j];
                    if (j >= c) {
                        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;
}