Cod sursa(job #1497599)

Utilizator akaprosAna Kapros akapros Data 6 octombrie 2015 23:31:51
Problema Balans Scor 5
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.04 kb
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iomanip>
#define maxN 152
#define p10 1000
using namespace std;
int m, r, c, n, i, j, maxv, st, dr, d[maxN * 2];
int 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("%d", &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(int x)
{
    int i, j, h;
    memset(sum, 0, 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, 0, 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;
}
int bs()
{
    int i = 0, p = 1 << 27;
    while (p)
    {
        if (i + p <= maxv && ok(i + p))
            i += p;
        p /= 2;
    }
    return i;
}
void write()
{
    int x;
    freopen("balans.out", "w", stdout);
    x = bs();
    double sol = (double)((double)(x * 1.000) / 1000.000);
    printf("%.3lf\n", (int)(sol * 1000) / 1000.0);
}
int main()
{
    read();
    write();
    return 0;
}