Submission #494817

#TimeUsernameProblemLanguageResultExecution timeMemory
494817nickmet2004Bigger segments (IZhO19_segments)C++11
100 / 100
89 ms20828 KiB
#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 (){
      |  ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...