Advertisement
Gosunov

Untitled

Jun 15th, 2022
100
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.76 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define all(a) (a).begin(), (a).end()
  4. #define int long long
  5.  
  6. const int maxn = 100500;
  7. int a[maxn];
  8. int pref[maxn];
  9. int mn[maxn];
  10.  
  11. void solve() {
  12.     int n;
  13.     cin >> n;
  14.     for (int i = 0; i < n; ++i) {
  15.         cin >> a[i];
  16.     }
  17.     int s = 0;
  18.     int ans = 0;
  19.     for (int i = 0; i < n; ++i) {
  20.         s += a[i];
  21.         mn[i + 1] = min(mn[i], s);
  22.         int l = -1;
  23.         int r = i + 1;
  24.         while (r - l > 1) {
  25.             int m = (l + r) / 2;
  26.             if (s - mn[m] > 0)
  27.                 r = m;
  28.             else
  29.                 l = m;
  30.         }
  31.         ans = max(ans, i - r + 1);
  32.     }
  33.     cout << ans << '\n';
  34. }
  35.  
  36. signed main() {
  37.     ios::sync_with_stdio(0); cin.tie(0);
  38.     solve();
  39. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement