Submission #490117

#	Time	Username	Problem	Language	Result	Execution time	Memory
490117		retsiger	Bigger segments (IZhO19_segments)	C++14	0 / 100	27 ms	62928 KiB

segments

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

using namespace std;
using ll = long long;

const int maxn = 500100, INF = 1e9;

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

int dp[4000][4000];

//int go(int i, ll cur) {
//  if (i > N) return 0;
//  int lo = i + 1, hi = N, p = i + 1;
//  while (lo <= hi) {
//    int mi = (lo + hi) >> 1;
//    if (S[mi] - S[i] >= cur) {
//      p = mi;
//      hi = mi - 1;
//    } else
//      lo = mi + 1;
//  }
//  return 1 + go(p, S[p] - S[i]);
//}

int main() {
  ios::sync_with_stdio(0); cin.tie(0);
//  freopen("cc.inp", "r", stdin);
//  freopen("cc.out", "w", stdout);
  cin >> N;
  memset(dp, -0x3f, sizeof dp);
  for (int i = 1; i <= N; ++i)
    cin >> A[i], S[i] = A[i] + S[i - 1], dp[0][i] = 1;
  int ans = 1;
//  for (int i = 1; i <= N; ++i) {
//    //ans = max(ans, go(i, S[i]));
//    cerr<<S[i]<<'\n';
//  }
  for (int r = 1; r <= N; ++r) {
    int i = r + 1, mx = -INF;
    for (int l = r - 1; l >= 0; --l) {
      while (i < N && S[i] - S[r] < S[r] - S[l]) {
        dp[r][i] = max(dp[r][i], mx + 1);
        ++i;
      }
//      cerr<<l<<' '<<r<<'\n';
//      bug(i)<<'\n';
//      break;
      mx = max(mx, dp[l][r]);
    }
    for (; i <= N; ++i) dp[r][i] = max(dp[r][i], mx + 1);
  }
  for (int i = 0; i < N; ++i) {
    ans = max(ans, dp[i][N]);
  }
  cout << ans << '\n';
  return 0;
}

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