Submission #590685

#	Time	Username	Problem	Language	Result	Execution time	Memory
590685		Hanksburger	Bigger segments (IZhO19_segments)	C++17	13 / 100	1 ms	352 KiB

segments

#include <bits/stdc++.h>
using namespace std;
int a[500005], sum[500005];
pair<int, int> dp[500005];
bool cmp(pair<int, int> x, pair<int, int> y)
{
    if (x.first!=y.first)
        return x.first<y.first;
    return x.second>y.second;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    for (int i=1; i<=n; i++)
    {
        cin >> a[i];
        sum[i]=sum[i-1]+a[i];
    }
    dp[1]={1, a[1]};
    for (int i=1; i<=n; i++)
    {
        int ind=lower_bound(sum+i+1, sum+n+1, dp[i].second+sum[i])-sum;
        if (ind<=n)
            dp[ind]=max(dp[ind], {dp[i].first+1, sum[ind]-sum[i]}, cmp);
        dp[i+1]=max(dp[i+1], {dp[i].first, dp[i].second+a[i+1]}, cmp);
    }
    cout << dp[n].first;
    return 0;
}

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