Submission #500054

#	Time	Username	Problem	Language	Result	Execution time	Memory
500054		RedBoy	Bigger segments (IZhO19_segments)	C++11	100 / 100	82 ms	13080 KiB

segments

#include <iostream>

using namespace std;

const int N = 5e5 + 5;

int n;
long long s[N];
pair<int, int> dp[N];

bool check(int mid, int index)
{
    return s[mid] >= 2 * s[index] - s[dp[index].second - 1];
}

int binarySearch(int index)
{
    int l = index + 1, r = n;
    while(l < r)
    {
        int mid = (l + r) / 2;
        if(check(mid, index))
            r = mid;
        else
            l = mid + 1;
    }

    return (check(l, index) ? l : -1);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

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

    dp[1] = {1, 1};
    for(int i = 1; i <= n; i++)
    {
        dp[i + 1] = max(dp[i + 1], dp[i]);

        int x = binarySearch(i);
        if(x != -1)
            dp[x] = max(dp[x], {dp[i].first + 1, i + 1});
    }

    cout << dp[n].first << '\n';

    return 0;
}

• Subtask 1: 13 / 13
• Subtask 2: 14 / 14
• Subtask 3: 10 / 10
• Subtask 4: 36 / 36
• Subtask 5: 27 / 27