Cod sursa(job #1497804)

Utilizator akaprosAna Kapros akapros Data 7 octombrie 2015 13:27:06
Problema Balans Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.09 kb
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iomanip>
#define maxN 152
#define p10 1000
#define ll long long
using namespace std;
int m, r, c, n, i, j;
ll maxv, st, dr, d[maxN * 2];
ll a[maxN * 2][maxN * 2], sum[maxN * 2][maxN * 2], s[maxN * 2][maxN * 2];
void read()
{
    freopen("balans.in", "r", stdin);
    scanf("%d %d %d %d", &n, &m, &r, &c);
    for (i = 1; i <= n; ++ i)
    {
        for (j = 1; j <= m; ++ j)
        {
            scanf("%lld", &a[i][j]);
            a[i][j] *= p10;
            a[i + n][j] = a[i][j];
            if (a[i][j] > maxv)
                maxv = a[i][j];
            a[i][j + m] = a[i][j];
            a[i + n][j + m] = a[i][j];
        }
    }
}
void right(int j)
{
    while (st <= dr && s[i][j - c] <= s[i][d[dr]])
        -- dr;
    d[++ dr] = j - c;
}
void left(int j)
{
    if (st <= dr && d[st] < j - m)
        ++ st;
}
int ok(ll x)
{
    int i, j, h;
    memset(sum, 0LL, sizeof(sum));
    for (i = 1; i <= n * 2; ++ i)
            for (j = 1; j <= 2 * m; ++ j)
                sum[i][j] = sum[i - 1][j] + a[i][j] - x;
    for (h = r; h <= n; ++ h)
    {
        memset(s, 0LL, sizeof(s));
        for (i = h; i <= n * 2; ++ i)
            for (j = 1; j <= 2 * m; ++ j)
                    s[i][j] = s[i][j - 1] + sum[i][j] - sum[i - h][j];

        for (i = h; i <= 2 * n; ++ i)
        {
            st = 1; dr = 0;
            for (j = c; j <= m * 2; ++ j)
            {
                right(j);
                left(j);
                if (s[i][j] - s[i][d[st]] >= 0)
                    return 1;
            }
        }
    }
    return 0;
}
long long bs()
{
    ll i = 0LL, p = 1 << 27;
    while (p)
    {
        if (i + p <= maxv && ok(i + p))
            i += p;
        p /= 2;
    }
    return i * 1LL;
}
void write()
{
    ll x;
    freopen("balans.out", "w", stdout);
    x = bs();
    long double sol = (double)((double)(x * 1.000 * 1LL) / 1000.000);
    printf("%.3lf\n", (int)(sol * 1000) / 1000.0);
}
int main()
{
    read();
    write();
    return 0;
}