Submission #988652

#	Time	Username	Problem	Language	Result	Execution time	Memory
988652		mannshah1211	Bigger segments (IZhO19_segments)	C++17	100 / 100	65 ms	13124 KiB

segments

/**
 *    author: tourist
 *    created:
**/
#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;
  vector<long long> a(n + 1);
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
    a[i] += a[i - 1];
  }
  vector<int> prv(n + 1), dp(n + 1);
  for (int i = 1; i <= n; i++) {
    prv[i] = max(prv[i], prv[i - 1]);
    dp[i] = dp[prv[i]] + 1;
    int pos = lower_bound(a.begin(), a.end(), a[i] + a[i] - a[prv[i]]) - a.begin();
    if (pos <= n) {
      prv[pos] = i;
    }
  }
  cout << dp[n] << '\n';
  return 0;
}

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