제출 #500054

#제출 시각아이디문제언어결과실행 시간메모리
500054RedBoyBigger segments (IZhO19_segments)C++11
100 / 100
82 ms13080 KiB
#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;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...