Submission #2774153


Source Code Expand

Copy
#include <bits/stdc++.h>
#define int long long
#define ff first
#define dd second
#define mp make_pair
#define pb push_back
#define pp pair<int,int>
#define N 200007 // check
#define K 13
using namespace std;

int n;

int tab[N];
int rev[N];

int pref[N];

int best = 1e17;

int get(int a, int b) {
    return pref[b+1]-pref[a];
}

int minimal(int a, int b) {
    int l = a; int p = b;
    while(p-l > 4) {
        int s = (l+p)/2;
        if(get(a,s)*2 <= get(a,b)) {
            l = s;
        } else {
            p = s;
        }
    }
    int res = 1e17;
    for(int i = l; i <= min(p+1,b-1); ++i) {
        res = min(res, abs(get(a,i)-get(i+1,b)));
    }
    return res;
}

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin >> n;
    for(int i = 0; i < n; ++i) cin >> tab[i];
    pref[0] = 0;
    for(int i = 1; i <= n; ++i) pref[i] = pref[i-1] + tab[i-1];

    for(int i = 0; i < n-1; ++i) {
        int a = abs((get(0,i)-minimal(0,i))/2 + minimal(0,i) - (get(i+1,n-1)-minimal(i+1,n-1))/2);
        int b = abs((get(i+1,n-1)-minimal(i+1,n-1))/2 + minimal(i+1,n-1) - (get(0,i)-minimal(0,i))/2);
        int c = minimal(0,i);
        int d = minimal(i+1,n-1);
        best = min(best, max(max(a,b),max(c,d)));
    }
    cout << best << endl;
}

Submission Info

Submission Time
Task D - Equal Cut
User atszcoder
Language C++14 (GCC 5.4.1)
Score 600
Code Size 1317 Byte
Status AC
Exec Time 55 ms
Memory 4480 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 2 ms 2304 KB
sample_02.txt AC 2 ms 2304 KB
sample_03.txt AC 2 ms 2304 KB
subtask_1_01.txt AC 2 ms 2304 KB
subtask_1_02.txt AC 53 ms 4224 KB
subtask_1_03.txt AC 24 ms 2944 KB
subtask_1_04.txt AC 36 ms 3328 KB
subtask_1_05.txt AC 2 ms 2304 KB
subtask_1_06.txt AC 7 ms 2560 KB
subtask_1_07.txt AC 31 ms 3200 KB
subtask_1_08.txt AC 19 ms 2944 KB
subtask_1_09.txt AC 30 ms 3200 KB
subtask_1_10.txt AC 42 ms 3840 KB
subtask_1_11.txt AC 49 ms 4096 KB
subtask_1_12.txt AC 23 ms 3072 KB
subtask_1_13.txt AC 33 ms 3200 KB
subtask_1_14.txt AC 11 ms 2560 KB
subtask_1_15.txt AC 7 ms 2560 KB
subtask_1_16.txt AC 26 ms 3072 KB
subtask_1_17.txt AC 23 ms 3072 KB
subtask_1_18.txt AC 3 ms 2304 KB
subtask_1_19.txt AC 47 ms 4224 KB
subtask_1_20.txt AC 54 ms 4224 KB
subtask_1_21.txt AC 27 ms 3072 KB
subtask_1_22.txt AC 18 ms 2816 KB
subtask_1_23.txt AC 46 ms 3840 KB
subtask_1_24.txt AC 54 ms 4480 KB
subtask_1_25.txt AC 54 ms 4480 KB
subtask_1_26.txt AC 53 ms 4480 KB
subtask_1_27.txt AC 53 ms 4480 KB
subtask_1_28.txt AC 53 ms 4480 KB
subtask_1_29.txt AC 54 ms 4480 KB
subtask_1_30.txt AC 54 ms 4480 KB
subtask_1_31.txt AC 54 ms 4480 KB
subtask_1_32.txt AC 55 ms 4480 KB
subtask_1_33.txt AC 54 ms 4480 KB
subtask_1_34.txt AC 51 ms 4480 KB
subtask_1_35.txt AC 51 ms 4480 KB
subtask_1_36.txt AC 50 ms 4480 KB
subtask_1_37.txt AC 51 ms 4480 KB