Cod sursa(job #1751187)

Utilizator TimitocArdelean Andrei Timotei Timitoc Data 31 august 2016 21:49:09
Problema Balans Scor 55
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.6 kb
#include <iostream>
#include <cstdio>
#define MAXN 164
#define MAXM 164

using namespace std;

int a[2*MAXN][2*MAXM];
int pre[2*MAXN][2*MAXN], deck[2*MAXM];;
double crt[2*MAXM];
int n, m, r, c;

void citire()
{
    scanf("%d %d %d %d", &n, &m, &r, &c);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) {
            scanf("%d", &a[i][j]);
            a[i][j+m] = a[i+n][j] = a[i+n][j+m] = a[i][j];
        }
    for (int i = 1; i <= 2*n; i++)
        for (int j = 1; j <= 2*m; j++)
            pre[i][j] = pre[i-1][j] + a[i][j];

}

int check(int stx, int len, double k)
{
    for (int i = 1; i <= 2*m; i++)
        crt[i] = crt[i-1] + pre[stx+len-1][i] - pre[stx-1][i] - (k*len);
    if (crt[c] >= 0) return 1;
    int st = 0, dr = -1;
    for (int i = c+1; i <= 2*m; i++) {
        while (st <= dr && crt[i-c] <= crt[deck[dr]])
            dr--;
        deck[++dr] = i-c;
        while (st < dr && i-deck[st]+1 > m)
            st++;
        double scad = crt[deck[st]];
        if (crt[i]-scad >= 0) return 1;
    }
    return 0;
}

void solve()
{
    double rez = -1;
    for (int i = 1; i <= n; i++)
        for (int j = r; j <= n; j++) {
            double k, lo = 0, hi = 1000000;
            while (hi - lo > 0.00008) {
                k = (lo + hi) / 2;
                if (check(i, j, k))
                    lo = k;
                else
                    hi = k;
            }
            if (lo > rez)
                rez = lo;
        }
    printf("%.3lf", rez);
}

int main()
{
    freopen("balans.in", "r", stdin);
    freopen("balans.out", "w", stdout);

    citire();
    solve();

    return 0;
}