Submission #238592

#	Time	Username	Problem	Language	Result	Execution time	Memory
238592		Aydarov03	Bigger segments (IZhO19_segments)	C++14	37 / 100	481 ms	262144 KiB

segments

#include <bits/stdc++.h>
#define pb push_back
#define pii pair<int, int>
#define fr first
#define sc second
#define int long long
using namespace std;

// ~30 points
const int N  = 3001;
const int INF = 1e18;

int dp[N][N];
int suf[N][N];
int pref[N], a[N];

int get(int l, int r) {
  if (l > r) {
    return -1e9;
  }
  return pref[r] - pref[l - 1];
}

main() {
  int n;
  cin >> n;
  for (int i = 1; i <= n; i++) {
    scanf("%lld", &a[i]);
    pref[i] = pref[i - 1] + a[i];
  }

  for (int i = 0; i <= n; i++) {
    for (int gr = 0; gr <= n; gr++) {
      suf[i][gr] = -INF;
    }
  }

  for (int lst = 1; lst <= n; lst++) {
    suf[1][lst] = 1;
  }

  for (int gr = 1; gr < n; gr++) {
    for (int i = 1; i <= n; i++) {
      suf[gr][i] = max(suf[gr][i - 1], suf[gr][i]);
    }
    for (int i = gr; i <= n; i++) {
      if (suf[gr][i] == -INF) {
        continue;
      }
      dp[gr][i] = get(suf[gr][i], i);
      int best = dp[gr][i];
      if (best > get(i + 1, n)) {
        continue;
      }
      int l = i, r = n + 1;
      while (r - l > 1) {
        int mid = l + r >> 1;
        if (get(i + 1, mid) >= dp[gr][i]) {
          r = mid;
        } else {
          l = mid;
        }
      }
      suf[gr + 1][r] = max(suf[gr + 1][r], i + 1);
    }
  }

/*
5
6 2 3 9 13
*/

//  for (int gr = 1; gr <= n; gr++) {
//    for (int i = 1; i <= n; i++) {
//      cout << suf[gr][i] << " ";
//    }cout << endl;
//  }puts("");

  int ans = 0;
  for (int gr = 1; gr <= n; gr++) {
    if (suf[gr][n] != -INF) {
      ans = max(ans, gr);
    }
  }
  cout << ans;
}

Compilation message (stderr)

segments.cpp:24:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^
segments.cpp: In function 'int main()':
segments.cpp:57:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int mid = l + r >> 1;
                   ~~^~~
segments.cpp:28:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld", &a[i]);
     ~~~~~^~~~~~~~~~~~~~~

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