Cod sursa(job #256884)

Utilizator MariusMarius Stroe Marius Data 12 februarie 2009 13:08:31
Problema Balans Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.06 kb
#include <fstream>
#include <iostream>
using namespace std;

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

#define FOR(i, a, b)  for (register 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 ret = -1000000000000LL, tmp;

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

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

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

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