CUBE-T164: Treasure

#include <iostream>
#include <vector>
#include <math.h>
using namespace std;

#define lli long long

vector<lli> room;
int nr;

lli Sum(int l, int r){
    return room[r] - room[l - 1];
}

lli MinDiff(){
    lli ans = 1e18;
    for(int i = 2; i <= nr - 1; ++i){
        lli s1 = Sum(1, i - 1);
        int l = i;
        int r = nr - 1;
        while(l <= r){
            int m = (l + r) / 2;
            lli s2, s3;
            lli d1 = abs(Sum(i, m - 1) - Sum(m, nr));
            lli d2 = abs(Sum(i, m) - Sum(m + 1, nr));
            if(d1 > d2){
                s2 = Sum(i, m);
                s3 = Sum(m + 1, nr);
                l = m + 1;
            } else {
                s2 = Sum(i, m - 1);
                s3 = Sum(m, nr);
                r = m - 1;
            }
            ans = min(ans, max(abs(s1 - s2), max(abs(s1 - s3), abs(s2 - s3))));
        }
    }
    return ans;
}

int main(){

    int x;

    scanf("%d", &nr);
    room.assign(nr + 1, 0);
    for(int i = 1; i <= nr; ++i){
        scanf("%d", &x);
        room[i] = room[i - 1] + x;
    }

    cout << MinDiff();

    return 0;
}