Submission #2777628


Source Code Expand

Copy
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
#define int ll

#define REP(i,n) for(int i=0;i<n;++i)
#define SORT(name) sort(name.begin(), name.end())
#define ZERO(p) memset(p, 0, sizeof(p))
#define MINUS(p) memset(p, -1, sizeof(p))
#if 0
#  define DBG(fmt, ...) printf(fmt, ##__VA_ARGS__)
#else
#  define DBG(fmt, ...)
#endif

const ll LLINF = (1LL<<60);
const int INF = (1LL<<30);
const int MOD = 1000000007;
#define MAX_N 200010

template< typename T >
class CumulativeSum
{
public:
    vector< T > m_data;
    CumulativeSum() {};
    CumulativeSum(int sz) : m_data(sz, 0) {};

    // k に x を加える O(1)
    void Add(int k, int x) {
        assert(m_data.size() >= k);
        if(m_data.size() <= k) { m_data.push_back(x); }
        else { m_data[k] += x; }
    }

    // 累積和の構築 O(m_data.size())
    void Build() { for(int i = 1; i < m_data.size(); i++) { m_data[i] += m_data[i - 1]; } }

    // 区間 [0, k] の和を返す O(1)
    // 閉区間なので k が含まれることに注意
    T Query(int k) {
        if(k < 0) { return 0; }
        return (m_data[min(k, (int) m_data.size() - 1)]);
    }

    // 区間 [l, h] の和を返す O(1)
    // 閉区間なので k が含まれることに注意
    T Query(int l, int h) { return this->Query(h) - this->Query(l-1); }
};


ll N;
ll A[MAX_N] = {};

signed main()
{
    CumulativeSum<ll> cs;

    cin >> N;
    REP(i, N) {
        cin >> A[i];
        cs.Add(i, A[i]);
    }
    cs.Build();

    ll ans = LLINF;
    for(int i = 1; i < N-2; ++i) {
        // 左部分が同じくらいの数になるようにぶたん
        ll lb = 0;
        ll ub = i;
        ll prev = -1;
        ll border1, border2;
        while(ub != lb) {
            ll mid = (ub - lb) / 2 + lb;
            border1 = mid;
            if(mid == prev) { break; }
            ll cand1 = LLINF, cand2 = LLINF, cand3 = LLINF;
            if(mid - 1 >= 0) {
                cand1 = abs(cs.Query(0, mid - 1) - cs.Query(mid, i));
            }
            if(mid + 1 <= i) {
                cand2 = abs(cs.Query(0, mid) - cs.Query(mid + 1, i));
            }
            if(mid + 2 <= i) {
                cand3 = abs(cs.Query(0, mid + 1) - cs.Query(mid + 2, i));
            }
            if(cand2 <= cand1 && cand2 <= cand3) {
                break;
            }
            else if(cand1 <= cand2 && cand1 <= cand3) {
                ub = mid;
            }
            else if(cand3 <= cand2 && cand3 <= cand1) {
                lb = mid;
            }
            prev = mid;
        }
        // 右部分が同じくらいの数になるようにぶたん
        prev = -1;
        lb = i + 1;
        ub = N - 1;
        while(ub != lb) {
            ll mid = (ub - lb) / 2 + lb;
            border2 = mid;
            if(mid == prev) { break; }
            ll cand1 = LLINF, cand2 = LLINF, cand3 = LLINF;
            if(mid - 1 >= i + 1) {
                cand1 = abs(cs.Query(i + 1, mid - 1) - cs.Query(mid, N - 1));
            }
            if(mid + 1 <= N - 1) {
                cand2 = abs(cs.Query(i + 1, mid) - cs.Query(mid + 1, N - 1));
            }
            if(mid + 2 <= N - 1) {
                cand3 = abs(cs.Query(i + 1, mid + 1) - cs.Query(mid + 2, N - 1));
            }
            if(cand2 <= cand1 && cand2 <= cand3) {
                break;
            }
            else if(cand1 <= cand2 && cand1 <= cand3) {
                ub = mid;
            }
            else if(cand3 <= cand2 && cand3 <= cand1) {
                lb = mid;
            }
            prev = mid;
        }
        ll P = cs.Query(0, border1);
        ll Q = cs.Query(border1 + 1, i);
        ll R = cs.Query(i + 1, border2);
        ll S = cs.Query(border2 + 1, N - 1);
        DBG("[%lld, %lld]] %lld\n", 0, border1, P);
        DBG("[%lld, %lld]] %lld\n", border1 + 1, i, Q);
        DBG("[%lld, %lld]] %lld\n", i + 1, border2, R);
        DBG("[%lld, %lld]] %lld\n", border2 + 1, N - 1, S);
        ll max_a = max({P, Q, R, S});
        ll min_a = min({P, Q, R, S});
        DBG("max: %lld min: %lld diff: %lld\n", max_a, min_a, abs(max_a - min_a));
        ans = min(ans, abs(max_a - min_a));
    }

    printf("%lld\n", ans);
    return 0;
}

Submission Info

Submission Time
Task D - Equal Cut
User VTR
Language C++14 (GCC 5.4.1)
Score 600
Code Size 4377 Byte
Status AC
Exec Time 136 ms
Memory 3568 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 600 / 600
Status
AC × 3
AC × 43
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt
All sample_01.txt, sample_02.txt, sample_03.txt, sample_01.txt, sample_02.txt, sample_03.txt, subtask_1_01.txt, subtask_1_02.txt, subtask_1_03.txt, subtask_1_04.txt, subtask_1_05.txt, subtask_1_06.txt, subtask_1_07.txt, subtask_1_08.txt, subtask_1_09.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_12.txt, subtask_1_13.txt, subtask_1_14.txt, subtask_1_15.txt, subtask_1_16.txt, subtask_1_17.txt, subtask_1_18.txt, subtask_1_19.txt, subtask_1_20.txt, subtask_1_21.txt, subtask_1_22.txt, subtask_1_23.txt, subtask_1_24.txt, subtask_1_25.txt, subtask_1_26.txt, subtask_1_27.txt, subtask_1_28.txt, subtask_1_29.txt, subtask_1_30.txt, subtask_1_31.txt, subtask_1_32.txt, subtask_1_33.txt, subtask_1_34.txt, subtask_1_35.txt, subtask_1_36.txt, subtask_1_37.txt
Case Name Status Exec Time Memory
sample_01.txt AC 1 ms 256 KB
sample_02.txt AC 1 ms 256 KB
sample_03.txt AC 1 ms 256 KB
subtask_1_01.txt AC 1 ms 256 KB
subtask_1_02.txt AC 134 ms 3444 KB
subtask_1_03.txt AC 52 ms 1912 KB
subtask_1_04.txt AC 91 ms 2292 KB
subtask_1_05.txt AC 1 ms 256 KB
subtask_1_06.txt AC 13 ms 768 KB
subtask_1_07.txt AC 69 ms 2164 KB
subtask_1_08.txt AC 42 ms 1912 KB
subtask_1_09.txt AC 66 ms 2164 KB
subtask_1_10.txt AC 90 ms 3444 KB
subtask_1_11.txt AC 109 ms 3444 KB
subtask_1_12.txt AC 51 ms 1912 KB
subtask_1_13.txt AC 73 ms 2292 KB
subtask_1_14.txt AC 22 ms 1148 KB
subtask_1_15.txt AC 14 ms 768 KB
subtask_1_16.txt AC 49 ms 2036 KB
subtask_1_17.txt AC 43 ms 1912 KB
subtask_1_18.txt AC 3 ms 384 KB
subtask_1_19.txt AC 94 ms 3444 KB
subtask_1_20.txt AC 136 ms 3444 KB
subtask_1_21.txt AC 59 ms 1912 KB
subtask_1_22.txt AC 43 ms 1272 KB
subtask_1_23.txt AC 101 ms 3444 KB
subtask_1_24.txt AC 113 ms 3444 KB
subtask_1_25.txt AC 115 ms 3444 KB
subtask_1_26.txt AC 116 ms 3444 KB
subtask_1_27.txt AC 118 ms 3444 KB
subtask_1_28.txt AC 116 ms 3444 KB
subtask_1_29.txt AC 113 ms 3444 KB
subtask_1_30.txt AC 118 ms 3444 KB
subtask_1_31.txt AC 116 ms 3444 KB
subtask_1_32.txt AC 117 ms 3444 KB
subtask_1_33.txt AC 118 ms 3444 KB
subtask_1_34.txt AC 97 ms 3444 KB
subtask_1_35.txt AC 102 ms 3444 KB
subtask_1_36.txt AC 102 ms 3444 KB
subtask_1_37.txt AC 101 ms 3568 KB