Submission #1007004

#	Time	Username	Problem	Language	Result	Execution time	Memory
1007004		kebine	Bigger segments (IZhO19_segments)	C++17	100 / 100	55 ms	18868 KiB

segments

#include<bits/stdc++.h>
#define int long long
#define fi first
#define se second

using namespace std;
const int maxn = 5e5;
bool debug = 1;

// dp[i] = maximum # segments if i is the end of the current segment
// pos[i] = last value of R that is lesser than i
// pref[i] - pref[pos[i]] >= pref[j] - pref[i] with j being the lb of the next segment
// 2*pref[i] - pref[pos[i]] >= pref[j]
// binary search and find the leftmost j (since we want to minimize the size of the current segment)
// pos[j] = i

int n;
int pref[maxn+5], dp[maxn+5], pos[maxn+5], a[maxn+5];

signed main() {
  ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  cin >> n;
  for (int i=1; i<=n; i++) {
    cin >> a[i];
    pref[i] = pref[i-1] + a[i];
  }
  dp[1] = 1; dp[0] = 0;
  pos[1] = 0; pos[0] = 0;
  for (int i=1; i<=n; i++) {
    int l = i+1, r = n, j = -1;
    pos[i] = max(pos[i], pos[i-1]);
    while (l <= r) {
      int mid = (l+r)/2;
      if (pref[mid] >= 2*pref[i] - pref[pos[i]]) {
        r = mid-1;
        j = mid;
      }
      else l = mid+1;
    }
    if (j != -1) {
      pos[j] = max(pos[j], i);
    } 
    dp[i] = max(dp[i], dp[pos[i]] + 1);
  }
  cout << dp[n] << endl;
  return 0;
}

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