Submission #590689

#	Time	Username	Problem	Language	Result	Execution time	Memory
590689		Hanksburger	Bigger segments (IZhO19_segments)	C++17	100 / 100	81 ms	20820 KiB

segments

#include <bits/stdc++.h>
using namespace std;
long long a[500005], sum[500005];
pair<long long, long long> dp[500005];
bool cmp(pair<long long, long long> x, pair<long long, long long> 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);
    long long n;
    cin >> n;
    for (long long i=1; i<=n; i++)
    {
        cin >> a[i];
        sum[i]=sum[i-1]+a[i];
    }
    dp[1]={1, a[1]};
    for (long long i=1; i<=n; i++)
    {
        long long 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: 14 / 14
• Subtask 3: 10 / 10
• Subtask 4: 36 / 36
• Subtask 5: 27 / 27