Submission #490122

#	Time	Username	Problem	Language	Result	Execution time	Memory
490122		retsiger	Bigger segments (IZhO19_segments)	C++14	100 / 100	78 ms	16024 KiB

segments

#include<bits/stdc++.h>
#define bug(x) cerr<<__LINE__<<": "<<#x<<" = "<<x<<'\n'
#define x first
#define y second

using namespace std;
using ll = long long;

const int maxn = 500100, INF = 1e9;

typedef pair<int, ll> ii;

int N, A[maxn];
ll S[maxn];

ii dp[maxn];

void maxx(ii &a, ii b) {
  if (a.x < b.x) {
    a = b;
  } else if (a.x == b.x) {
    if (a.y > b.y) a = b;
  }
  return;
}

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];
  dp[1] = {1, A[1]};
  for (int i = 1; i <= N; ++i) {
    ll sum = dp[i].y;
    int lo = i + 1, hi = N, p = -1;
    while (lo <= hi) {
      int mi = (lo + hi) >> 1;
      if (S[mi] - S[i] >= sum) {
        p = mi;
        hi = mi - 1;
      } else
        lo = mi + 1;
    }
    if (p != -1) {
      maxx(dp[p], {dp[i].x + 1, S[p] - S[i]});
    }
    maxx(dp[i + 1], {dp[i].x, dp[i].y + A[i + 1]});
  }
  cout << dp[N].x << '\n';
  return 0;
}

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