Submission #490112

#TimeUsernameProblemLanguageResultExecution timeMemory
490112retsigerBigger segments (IZhO19_segments)C++14
0 / 100
0 ms332 KiB
#include<bits/stdc++.h>
#define bug(x) cerr<<__LINE__<<": "<<#x<<" = "<<x<<'\n'

using namespace std;
using ll = long long;

const int maxn = 500100;

int N, A[maxn];
ll S[maxn];

int go(int i, ll cur) {
  if (i > N) return 0;
  int lo = i + 1, hi = N, p = i + 1;
  while (lo <= hi) {
    int mi = (lo + hi) >> 1;
    if (S[mi] - S[i] >= cur) {
      p = mi;
      hi = mi - 1;
    } else
      lo = mi + 1;
  }
  return 1 + go(p, S[p] - S[i]);
}

int main() {
  ios::sync_with_stdio(0); cin.tie(0);
//  freopen("cc.inp", "r", stdin);
//  freopen("cc.out", "w", stdout);
  cin >> N;
  for (int i = 1; i <= N; ++i)
    cin >> A[i], S[i] = A[i] + S[i - 1];
  int ans = 0;
  for (int i = 1; i <= N; ++i) {
    ans = max(ans, go(i, S[i]));
  }
  cout << ans << '\n';
  return 0;
}
#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...