Cod sursa(job #788897)

Utilizator a_h1926Heidelbacher Andrei a_h1926 Data 16 septembrie 2012 01:12:34
Problema Balans Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.9 kb
#include <cstdio>
#include <algorithm>

using namespace std;

typedef long long LL;

const int MaxN = 305;

int N, M, R, C, A[MaxN][MaxN], AMax, AMin, Solution;
LL SumC[MaxN][MaxN], Sum[MaxN];
int D[MaxN];

inline bool MSS() {
    LL MaxS = Sum[C];
    int F=1, B=0; D[1] = 0;
    for (int i = C; i <= M+M; ++i) {
        for (; F <= B && D[F] < i-M; ++F);
        for (; F <= B && Sum[i-C+1] <= Sum[D[B]]; --B);
        D[++B] = i-C;
        MaxS = max(MaxS, Sum[i]-Sum[D[F]]);
        if (D[F] > M)
            break;
    }
    return MaxS >= 0;
}

inline void BuildSum(const int L1, const int L2, const int S) {
    Sum[0] = 0;
    for (int i = 1; i <= M+M; ++i)
        Sum[i] = Sum[i-1]+SumC[L2][i]-SumC[L1-1][i]-1LL*(L2-L1+1)*S;
}

inline bool FindMSM(const int S) {
    for (int L1 = 1; L1 <= N; ++L1) {
        for (int L2 = L1+R-1; L2 <= L1+N-1; ++L2) {
             BuildSum(L1, L2, S);
             if (MSS())
                 return true;
        }
    }
    return false;
}

void Solve() {
    int L = AMin, R = AMax;
    while (L <= R) {
        int Mid = (L+R)/2;
        if (FindMSM(Mid))
            Solution=Mid, L=Mid+1;
        else
            R=Mid-1;
    }
}

void Read() {
    freopen("balans.in", "r", stdin);
    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] *= 1000;
            A[i+N][j] = A[i][j+M] = A[i+N][j+M] = A[i][j];
            AMax = max(AMax, A[i][j]);
            AMin = min(AMin, A[i][j]);
        }
    }
    for (int i=1; i <= N+N; ++i)
        for (int j=1; j <= M+M; ++j)
            SumC[i][j] = SumC[i-1][j]+A[i][j];
}

void Print() {
    freopen("balans.out", "w", stdout);
    printf("%.3lf\n", (1.0*Solution)/1000.0);
}

int main() {
    Read();
    Solve();
    Print();
    return 0;
}