Submission #2773841


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();

    // だいたい 3 倍くらいになる場所を求める
    pair<int ,int> cand1 = {0, LLINF};
    for(int i = 0; i < N-4; ++i) {
        ll left = cs.Query(0, i);
        ll right = cs.Query(i+1, N-1);
        ll sub = abs(left * 3 - right);
        if(cand1.second > sub) { cand1= {i, sub}; }
    }

    pair<int ,int> cand2 = {0, LLINF};
    for(int i = 0; i < N-2; ++i) {
        ll left = cs.Query(0, i);
        ll right = cs.Query(i+1, N-1);
        ll sub = abs(left - right);
        if(cand2.second > sub) { cand2= {i, sub}; }
    }

    pair<int ,int> cand3 = {0, LLINF};
    for(int i = 3; i < N-1; ++i) {
        ll left = cs.Query(0, i);
        ll right = cs.Query(i, N-1);
        ll sub = abs(left - right * 3);
        if(cand3.second > sub) { cand3= {i, sub}; }
    }

    ll ans = LLINF;
    for(int i = -500; i <= 500; ++i) {
        ll border1 = cand1.first + i;
        if(border1 < 0 || border1 > N - 4) { continue; }
        for(int j = -500; j <= 500; ++j) {
            ll border2 = cand2.first + j;
            if(border2 <= border1 || border2 > N - 3) { continue; }
            for(int k = -500; k <= 500; ++k) {
                ll border3 = cand3.first + k;
                if(border3 <= border2 || border3 > N - 2) { continue; }
                ll max_a = 0;
                ll min_a = LLINF;
                DBG("[%lld, %lld]: %lld\n", 0, border1, cs.Query(0, border1));
                DBG("[%lld, %lld]: %lld\n", border1+1, border2, cs.Query(border1+1, border2));
                DBG("[%lld, %lld]: %lld\n", border2+1, border3, cs.Query(border2+1, border3));
                DBG("[%lld, %lld]: %lld\n", border3+1, N-1, cs.Query(border3+1, N-1));
                max_a = max(max_a, cs.Query(0, border1));
                max_a = max(max_a, cs.Query(border1 + 1, border2));
                max_a = max(max_a, cs.Query(border2 + 1, border3));
                max_a = max(max_a, cs.Query(border3 + 1, N - 1));
                min_a = min(min_a, cs.Query(0, border1));
                min_a = min(min_a, cs.Query(border1 + 1, border2));
                min_a = min(min_a, cs.Query(border2 + 1, border3));
                min_a = min(min_a, cs.Query(border3 + 1, N - 1));
                ans = min(ans, abs(max_a - min_a));
                DBG("ans: %lld cand: %lld\n", 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 0
Code Size 4023 Byte
Status WA
Exec Time 2103 ms
Memory 3444 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 600
Status
AC × 3
AC × 9
WA × 11
TLE × 23
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 TLE 2103 ms 3444 KB
subtask_1_03.txt TLE 2103 ms 1912 KB
subtask_1_04.txt TLE 2103 ms 2292 KB
subtask_1_05.txt AC 25 ms 256 KB
subtask_1_06.txt WA 252 ms 768 KB
subtask_1_07.txt TLE 2103 ms 2164 KB
subtask_1_08.txt TLE 2103 ms 1912 KB
subtask_1_09.txt TLE 2103 ms 2036 KB
subtask_1_10.txt TLE 2103 ms 3444 KB
subtask_1_11.txt TLE 2103 ms 3444 KB
subtask_1_12.txt WA 1401 ms 1912 KB
subtask_1_13.txt TLE 2103 ms 2292 KB
subtask_1_14.txt WA 599 ms 1148 KB
subtask_1_15.txt TLE 2103 ms 768 KB
subtask_1_16.txt WA 264 ms 2036 KB
subtask_1_17.txt WA 1622 ms 1912 KB
subtask_1_18.txt WA 690 ms 384 KB
subtask_1_19.txt TLE 2103 ms 3444 KB
subtask_1_20.txt TLE 2103 ms 3444 KB
subtask_1_21.txt TLE 2103 ms 1912 KB
subtask_1_22.txt TLE 2103 ms 1272 KB
subtask_1_23.txt TLE 2103 ms 3444 KB
subtask_1_24.txt WA 1085 ms 3444 KB
subtask_1_25.txt TLE 2103 ms 3444 KB
subtask_1_26.txt WA 1089 ms 3444 KB
subtask_1_27.txt TLE 2103 ms 3444 KB
subtask_1_28.txt AC 636 ms 3444 KB
subtask_1_29.txt TLE 2103 ms 3444 KB
subtask_1_30.txt TLE 2103 ms 3444 KB
subtask_1_31.txt TLE 2103 ms 3444 KB
subtask_1_32.txt TLE 2103 ms 3444 KB
subtask_1_33.txt TLE 2103 ms 3444 KB
subtask_1_34.txt WA 281 ms 3444 KB
subtask_1_35.txt WA 1641 ms 3444 KB
subtask_1_36.txt WA 730 ms 3444 KB
subtask_1_37.txt TLE 2103 ms 3444 KB