Submission #344974

#	Time	Username	Problem	Language	Result	Execution time	Memory
344974		jenkinsser	Bigger segments (IZhO19_segments)	C++17	100 / 100	101 ms	20972 KiB

segments

#include<bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define st first
#define nd second
#define pii pair<int,int>
#define N 500005
#define INF 1e9+5
#define sp " "
#define nl "\n"
#define fastio() ios_base::sync_with_stdio(0);cin.tie(0);
#define all(x) (x).begin(),(x).end()
#define ll long long
#define int ll
using namespace std;

int n,a[N],pre[N],dp[N],mx[N],idx;

int32_t main(){
    ios_base::sync_with_stdio(0),cin.tie(0);
    cin >> n;
    for(int i=1;i<=n;i++){
        cin >> a[i];
        pre[i]=pre[i-1]+a[i];
    }

    for(int i=1;i<=n;i++){
        mx[i]=max(mx[i],mx[i-1]);
        dp[i]=max(dp[i-1],dp[mx[i]]+1);
        idx=lower_bound(pre,pre+n+1,2*pre[i]-pre[mx[i]])-pre;
        mx[idx]=max(mx[idx],i);
    }
    cout << dp[n];
}

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