Submission #891599

#TimeUsernameProblemLanguageResultExecution timeMemory
891599Hovhannes1234Bigger segments (IZhO19_segments)C++17
13 / 100
1 ms2648 KiB
#include <bits/stdc++.h> using namespace std; const int N=5e5+5; int a[N]; pair <long long, long long> dp[N]; int main() { int n; cin>>n; for(int i=1; i<=n; i++){ cin>>a[i]; a[i] += a[i-1]; } dp[0].first = 1; for(int i = 1; i <= n; ++i){ dp[i] = max(dp[i], dp[i - 1]); auto ind = lower_bound(a + 1, a + n + 1, 2 * a[i] - dp[i].second) - a; dp[ind] = max(dp[ind],{ dp[i].first + 1, a[i]}); } cout << dp[n].first; }
#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...