Submission #1268342

#	Time	Username	Problem	Language	Result	Execution time	Memory
1268342		nai0610	Bigger segments (IZhO19_segments)	C++20	100 / 100	68 ms	12508 KiB

segments

#include<bits/stdc++.h>
#define ll int64_t
#define ld long double
using namespace std;
const int maxn=5e5+5;
int n;
pair<int,ll> f[maxn];
ll a[maxn];
int main(){
    //freopen("../input.inp","r",stdin);
    //freopen("output.out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    clock_t start,end;
    start=clock();
    cin >>n;
    for (int i=1;i<=n;i++) cin >>a[i];
    // reverse(a+1,a+1+n);
    for (int i=1;i<=n;i++) a[i]+=a[i-1];
    f[0]={1,0};
    for (int i=1;i<=n;i++) {
        f[i]=max(f[i],f[i-1]);
        int j=lower_bound(a+1,a+1+n,a[i]*2-f[i].second)-a;
        f[j]=max(f[j],{f[i].first+1,a[i]});
    }
    cout <<f[n].first;
    end=clock();
    cerr <<(ld) (end-start)/(ld)(CLOCKS_PER_SEC)*(1000.0L)<<'\n';
    return 0;
}

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