제출 #1247888

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1247888		tvgk	도넛 (JOI14_ho_t3)	C++20	100 / 100	82 ms	2756 KiB

2014_ho_t3

#include<bits/stdc++.h>
using namespace std;
#define task "a"
#define se second
#define fi first
#define ll long long
#define ii pair<ll, ll>
const long mxN = 1e5 + 7;

int n, a[mxN * 2];
ll pre[mxN * 2];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    //freopen(task".INP", "r", stdin);
    //freopen(task".OUT", "w", stdout);

    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        a[i + n] = a[i];
    }

    for (int i = 1; i <= 2 * n; i++)
        pre[i] = pre[i - 1] + a[i];

    ll ans = 0;
    for (int i = 0; i < n; i++)
    {
        ll l = 0, r = n;
        while (l <= r)
        {
            int mid = (l + r) / 2;

            int j = i + mid;
            int k = lower_bound(pre + j + 1, pre + n + i, pre[j] + pre[j] - pre[i]) - pre;

            if (pre[i + n] - pre[k] >= pre[j] - pre[i])
            {
                l = mid + 1;
                ans = max(ans, pre[j] - pre[i]);
            }
            else
                r = mid - 1;
        }
    }
    cout << ans;
}

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