提出 #21472485

ソースコード 拡げる

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#define all(x) (x).begin(),(x).end()
//#pragma GCC optimize ("-O3")
using namespace std;
void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
typedef long long ll; const int inf = INT_MAX / 2; const ll infl = 1LL << 60;
template<class T>bool chmax(T& a, const T& b) { if (a < b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T& a, const T& b) { if (b < a) { a = b; return 1; } return 0; }
//---------------------------------------------------------------------------------------------------
template<typename Func>
int findMin(int L, int R, Func f) { //[L, R)
    int lo = L - 1, hi = R - 1;
    while (lo + 1 != hi) {
        int mi = (lo + hi) / 2;
        if (f(mi) <= f(mi + 1)) hi = mi;
        else lo = mi;
    }
    return hi;
}
/*---------------------------------------------------------------------------------------------------
　　　　　　　　　　　 ∧＿∧
　　　　　 ∧＿∧ 　（´<_｀ ）　 Welcome to My Coding Space!
　　　　 （ ´_ゝ`）　/　 ⌒i     @hamayanhamayan0
　　　　／　　　＼　 　  |　|
　　　 /　　 /￣￣￣￣/　　|
　 ＿_(__ﾆつ/　    ＿/ .| .|＿＿＿＿
　 　　　＼/＿＿＿＿/　（u　⊃
---------------------------------------------------------------------------------------------------*/














int N; ll A[401010];
//---------------------------------------------------------------------------------------------------
ll tot = 0;
int st;
ll f(int len) {
    ll X = A[st + len - 1];
    if (st) X -= A[st - 1];
    ll Y = tot - X;
    return abs(X - Y);
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> A[i];
    rep(i, 0, N) tot += A[i];
    rep(i, 0, N) A[i + N] = A[i];
    rep(i, 1, N * 2) A[i] += A[i - 1];
    
    ll ans = infl;
    rep(_st, 0, N) {
        st = _st;
        int opt = findMin(1, N + 1, f);
        chmin(ans, f(opt));
    }
    cout << ans << endl;
}

提出情報

提出日時
問題 I - ピザ
ユーザ hamayanhamayan
言語 C++ (GCC 9.2.1)
得点 6
コード長 2258 Byte
結果 AC
実行時間 53 ms
メモリ 6752 KiB

ジャッジ結果

セット名 Sample All
得点 / 配点 0 / 0 6 / 6
結果
AC × 2
AC × 57
セット名 テストケース
Sample sample_01.txt, sample_02.txt
All hand2_01.txt, hand2_02.txt, hand2_03.txt, hand2_04.txt, hand2_05.txt, hand_01.txt, hand_02.txt, hand_03.txt, hand_04.txt, hand_05.txt, hand_06.txt, hand_07.txt, hand_08.txt, hand_09.txt, hand_10.txt, random_01.txt, random_02.txt, random_03.txt, random_04.txt, random_05.txt, random_06.txt, random_07.txt, random_08.txt, random_09.txt, random_10.txt, random_11.txt, random_12.txt, random_13.txt, random_14.txt, random_15.txt, random_16.txt, random_17.txt, random_18.txt, random_19.txt, random_20.txt, random_21.txt, random_22.txt, random_23.txt, random_24.txt, random_25.txt, random_26.txt, random_27.txt, random_28.txt, random_29.txt, random_30.txt, random_31.txt, random_32.txt, random_33.txt, random_34.txt, random_35.txt, random_36.txt, random_37.txt, random_38.txt, random_39.txt, random_40.txt, sample_01.txt, sample_02.txt
ケース名 結果 実行時間 メモリ
hand2_01.txt AC 8 ms 3600 KiB
hand2_02.txt AC 2 ms 3564 KiB
hand2_03.txt AC 6 ms 3584 KiB
hand2_04.txt AC 2 ms 3524 KiB
hand2_05.txt AC 3 ms 3564 KiB
hand_01.txt AC 48 ms 6724 KiB
hand_02.txt AC 51 ms 6728 KiB
hand_03.txt AC 48 ms 6720 KiB
hand_04.txt AC 51 ms 6640 KiB
hand_05.txt AC 52 ms 6588 KiB
hand_06.txt AC 50 ms 6656 KiB
hand_07.txt AC 52 ms 6636 KiB
hand_08.txt AC 52 ms 6584 KiB
hand_09.txt AC 53 ms 6656 KiB
hand_10.txt AC 52 ms 6588 KiB
random_01.txt AC 50 ms 6724 KiB
random_02.txt AC 53 ms 6584 KiB
random_03.txt AC 52 ms 6640 KiB
random_04.txt AC 52 ms 6752 KiB
random_05.txt AC 53 ms 6752 KiB
random_06.txt AC 53 ms 6640 KiB
random_07.txt AC 51 ms 6728 KiB
random_08.txt AC 49 ms 6584 KiB
random_09.txt AC 50 ms 6748 KiB
random_10.txt AC 52 ms 6636 KiB
random_11.txt AC 38 ms 5332 KiB
random_12.txt AC 32 ms 5132 KiB
random_13.txt AC 45 ms 6300 KiB
random_14.txt AC 39 ms 5684 KiB
random_15.txt AC 3 ms 3800 KiB
random_16.txt AC 43 ms 5700 KiB
random_17.txt AC 8 ms 3912 KiB
random_18.txt AC 46 ms 6384 KiB
random_19.txt AC 20 ms 4716 KiB
random_20.txt AC 15 ms 4280 KiB
random_21.txt AC 33 ms 5480 KiB
random_22.txt AC 30 ms 5028 KiB
random_23.txt AC 50 ms 6360 KiB
random_24.txt AC 42 ms 6072 KiB
random_25.txt AC 12 ms 3940 KiB
random_26.txt AC 6 ms 3700 KiB
random_27.txt AC 21 ms 4816 KiB
random_28.txt AC 26 ms 4564 KiB
random_29.txt AC 40 ms 5756 KiB
random_30.txt AC 28 ms 5304 KiB
random_31.txt AC 42 ms 6416 KiB
random_32.txt AC 13 ms 4080 KiB
random_33.txt AC 29 ms 5188 KiB
random_34.txt AC 25 ms 4808 KiB
random_35.txt AC 40 ms 5940 KiB
random_36.txt AC 39 ms 5888 KiB
random_37.txt AC 11 ms 3808 KiB
random_38.txt AC 48 ms 6508 KiB
random_39.txt AC 19 ms 4504 KiB
random_40.txt AC 14 ms 4264 KiB
sample_01.txt AC 3 ms 3584 KiB
sample_02.txt AC 2 ms 3564 KiB