Submission #899042

#	Time	Username	Problem	Language	Result	Execution time	Memory
899042		d4xn	Bigger segments (IZhO19_segments)	C++17	100 / 100	107 ms	45384 KiB

segments

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int N = 5e5+1, inf = LLONG_MAX;

int n, a[N], pre[N];
vector<pair<int, int>> dp[N];

signed main() {
  ios::sync_with_stdio(false); cin.tie(nullptr);

  cin >> n;
  a[0] = pre[0] = 0;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
    pre[i] = a[i] + pre[i-1];
  }

  dp[0].push_back(make_pair(0, 0));
  for (int i = 0; i < n; i++) {  
    pair<int, int> p = make_pair(-inf, inf);
    for (auto& [x, y] : dp[i]) {
      if (x > p.first) {
        p = make_pair(x, y);
      }
      else if (x == p.first) {
        p.second = min(p.second, y);
      }
    }

    // no hago grupo nuevo
    dp[i+1].push_back(make_pair(p.first, p.second + a[i+1]));

    // hago grupo nuevo
    int l = i+1;
    int r = n+1;
    while (l < r) {
      int mid = (l+r)/2;

      int x = pre[mid] - pre[i];
      if (x >= p.second) r = mid;
      else l = mid+1;
    }
    if (r == n+1) continue; // cogiendo todos sigue siendo menor

    dp[l].push_back(make_pair(p.first+1, pre[l] - pre[i]));
  }

  int ans = -inf;
  for (auto& [x, y] : dp[n]) {
    ans = max(ans, x);
  }
  cout << ans << "\n";
}

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