Submission #238580

#	Time	Username	Problem	Language	Result	Execution time	Memory
238580		Aydarov03	Bigger segments (IZhO19_segments)	C++14	13 / 100	27 ms	35712 KiB

segments

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

// ~30 points
const int N  = 3005;

int dp[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("%d", &a[i]);
    pref[i] = pref[i - 1] + a[i];
  }

  memset (dp, -1, sizeof dp);
  for (int lst = 1; lst <= n; lst++) {
    dp[lst][1] = pref[lst];
  }

  for (int gr = 1; gr < n; gr++) {
    for (int i = gr; i <= n; i++) {
      if (dp[i][gr] == -1) {
        continue;
      }
      if (dp[i][gr] > 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[i][gr]) {
          r = mid;
        } else {
          l = mid;
        }
      }
      for (int j = r; j <= n; j++) {
        if (dp[j][gr + 1] == -1) {
          dp[j][gr + 1] = get(i + 1, j);
        } else {
          dp[j][gr + 1] = min(dp[j][gr + 1], get(i + 1, j));
        }
      }
    }
  }
  int ans = 0;
  for (int gr = 1; gr <= 3000; gr++) {
    if (dp[n][gr] != -1) {
      ans = max(ans, gr);
    }
  }
  cout << ans;
}

Compilation message (stderr)

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

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