Submission #490112

#	Time	Username	Problem	Language	Result	Execution time	Memory
490112		retsiger	Bigger segments (IZhO19_segments)	C++14	0 / 100	0 ms	332 KiB

segments

#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;
}

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