Submission #1293355

#	Time	Username	Problem	Language	Result	Execution time	Memory
1293355		haha	Bigger segments (IZhO19_segments)	C++20	100 / 100	59 ms	14148 KiB

segments

#include <bits/stdc++.h>
#define f first
#define s second
#define ll long long
using namespace std;
const int maxn=5e5+5;

int n;
int a[maxn];
pair<int,ll> dp[maxn];
ll sum[maxn];

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        sum[i]=sum[i-1]+a[i];
    }
    dp[0]={1,0};
    for(int i=1;i<=n;i++){
        dp[i]=max(dp[i],dp[i-1]);
        ll val=2*sum[i]-dp[i].s;
        int j=lower_bound(sum+i,sum+n+1,val)-sum;
        dp[j]=max(dp[j],make_pair(dp[i].f+1,sum[i]));
    }
    cout<<dp[n].f;
}

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