USACO Contest March 2014 - Sabotage

#include <cstdio>
#include <fstream>

using namespace std;

ifstream fin("sabotage.in");
FILE *fout = fopen("sabotage.out", "w");

double L[100005], M[100005], R[100005];
int N;

bool ok(double k)
{
    for(int i = 1; i <= N; i++)
        L[i] = L[i-1] + M[i] - k;

    double minRight = 999999;

    R[N] = M[N] - k;
    R[N-1] = R[N] + M[N-1] - k;

    for(int i = N-2; i >= 1; i--)
    {
        minRight = min(minRight, R[i+2]);

        if(minRight + L[i] <= 0)
            return true;

        R[i] = R[i+1] + M[i] - k;
    }

    return false;
}

int main()
{
    fin >> N;

    for(int i = 1; i <= N; i++)
        fin >> M[i];

    double a = 1, b = 10005;
    double p = (a+b) / 2;

    for(int i = 1; i <= 100; i++)
    {
        if(ok(p))
            b = p;
        else
            a = p;

        p = (a+b) / 2;
    }

    fprintf(fout, "%.3f\n", p);
}