제출 #899036

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
899036		vjudge1	Bigger segments (IZhO19_segments)	C++17	37 / 100	53 ms	71260 KiB

segments

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int N = 3e3+3, inf = LLONG_MAX;

int n, a[N], pre[N], dp[N][N];

signed main() {
  ios::sync_with_stdio(false); cin.tie(nullptr);

  for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
      dp[i][j] = inf;
    }
  }

  cin >> n;
  a[0] = pre[0] = 0;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
    pre[i] = a[i] + pre[i-1];
  }

  dp[0][0] = 0;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j <= i; j++) {
      if (dp[i][j] == inf) continue;

      // no hago grupo nuevo
      dp[i+1][j] = min(dp[i+1][j], dp[i][j] + a[i+1]);

      // hago grupo nuevo
      int l = i+1;
      int r = n+1;
      while (l < r) {
        int mid = (l+r)/2;

        int x = pre[mid] - pre[i];
        if (x >= dp[i][j]) r = mid;
        else l = mid+1;
      }
      if (r == n+1) continue; // cogiendo todos sigue siendo menor

      dp[l][j+1] = min(dp[l][j+1], pre[l] - pre[i]);
    }
  }

  int ans;
  for (int i = n; i >= 1; i--) {
    if (dp[n][i] != inf) {
      ans = i;
      break;
    }
  }
  cout << ans << "\n";
}

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