Submission #490119

#	Time	Username	Problem	Language	Result	Execution time	Memory
490119		retsiger	Bigger segments (IZhO19_segments)	C++14	37 / 100	643 ms	139760 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 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) {
//    cerr<<S[i]<<'\n';
//  }
  for (int r = 1; r <= N; ++r) {
    int i = r, 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;
      }
      mx = max(mx, dp[l][r]);
      ///for (int i = r + 1; i <= N; ++i) if (S[i] - S[r] >= S[r] - S[l]) {
      ///  dp[r][i] = max(dp[r][i], dp[l][r] + 1);
      ///}
    }
    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: 13 / 13
• Subtask 2: 14 / 14
• Subtask 3: 10 / 10
• Subtask 4: 0 / 36
• Subtask 5: 0 / 27