Submission #991142

#	Time	Username	Problem	Language	Result	Execution time	Memory
991142		gmroh06	도넛 (JOI14_ho_t3)	C++14	100 / 100	349 ms	4692 KiB

2014_ho_t3

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

inline void fastio();

ll n, arr[200001], sum[200001], ans, mx;

int main() {
    fastio();

    cin >> n;

    for (ll i = 0; i < n; i++) {
        cin >> arr[i];
        arr[i + n] = arr[i];
        mx = max(mx, arr[i]);
    }

    for (ll i = 0; i < 2 * n; i++) {
        sum[i + 1] = sum[i] + arr[i];
    }

    for (ll i = 0; i < n; i++) {
        ll s = 0, e = sum[2 * n];

        while (s - e + 1 < 0) {
            ll m = (s + e) / 2;
            bool chk = true;

            for (ll j = 0, loc = i; j < 3; j++) {
                loc = lower_bound(sum, sum + 2 * n + 1, m + sum[loc]) - sum;

                if (loc > i + n) {
                    chk = false;
                    break;
                }
            }

            if (chk) {
                s = m;
            } else {
                e = m;
            }
        }

        ans = max(ans, s);
    }

    cout << ans << '\n';
}

inline void fastio() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
}

• Subtask 1: 5 / 5
• Subtask 2: 15 / 15
• Subtask 3: 30 / 30
• Subtask 4: 50 / 50