Submission #494817

#	Time	Username	Problem	Language	Result	Execution time	Memory
494817		nickmet2004	Bigger segments (IZhO19_segments)	C++11	100 / 100	89 ms	20828 KiB

segments

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6 + 5;
int n , a[N] , dp[N] , b[N] , p[N];
 main (){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n;
    for(int i = 1; i<= n;++i)cin >> a[i];
    for(int i  =1;i <= n; ++i) p[i] = p[i - 1] + a[i];
    for(int i = 1; i<= n; ++i){
        b[i] = max(b[i] , b[i - 1]);
        dp[i]= dp[b[i]] + 1;
        int x= lower_bound(p + 1 , p + 1 + n , 2*p[i] - p[b[i]]) - p;
        b[x] = max(b[x] , i);
    }cout << dp[n];
}

Compilation message (stderr)

segments.cpp:6:2: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
    6 |  main (){
      |  ^~~~

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