Submission #545420

#	Time	Username	Problem	Language	Result	Execution time	Memory
545420		krit3379	Bigger segments (IZhO19_segments)	C++17	100 / 100	90 ms	16944 KiB

segments

#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#define N 500005

long long a[N];
pair<int,long long> dp[N];

int main(){
    int n,i;
    scanf("%d",&n);
    for(i=1;i<=n;i++)scanf("%lld",&a[i]),a[i]+=a[i-1];
    dp[0]={1,0};
    for(i=1;i<=n;i++){
        dp[i]=max(dp[i],dp[i-1]);
        int pos=lower_bound(a+1,a+n+1,2*a[i]-dp[i].second)-a;
        dp[pos]=max(dp[pos],{dp[i].first+1,a[i]});
    }
    printf("%d",dp[n].first);
    return 0;
}

Compilation message (stderr)

segments.cpp: In function 'int main()':
segments.cpp:12:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 |     scanf("%d",&n);
      |     ~~~~~^~~~~~~~~
segments.cpp:13:27: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 |     for(i=1;i<=n;i++)scanf("%lld",&a[i]),a[i]+=a[i-1];
      |                      ~~~~~^~~~~~~~~~~~~~

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