Submission #96695

#	Time	Username	Problem	Language	Result	Execution time	Memory
96695		fjchf02	Split the sequence (APIO14_sequence)	C++98	100 / 100	1299 ms	81788 KiB

sequence

#include <bits/stdc++.h>

using namespace std;

const int N = 100010;
const long long inf = 4e18;

int n, m;
long long pref[N];
long long dp[N], new_dp[N];
int g[233][N];

void solve(int ph, int L, int R, int x, int y) {
  if (L > R) {
    return;
  }
  long long mx = -inf;
  int bid = -1;
  int cur = (L + R) >> 1;
  for (int i = x; i <= min(y, cur - 1); i++) {
    if (dp[i] == -inf) {
      continue;
    }
    long long c = dp[i] + (pref[cur] - pref[i]) * pref[i];
    if (c > mx) {
      mx = c;
      bid = i;
    }
  }
  new_dp[cur] = mx;
  g[ph][cur] = bid;
  solve(ph, L, cur - 1, x, bid);
  solve(ph, cur + 1, R, max(x, bid), y);
}

void print(int x, int y) {
  if (x == 0) {
    assert(y == 0);
    return;
  }
  print(x - 1, g[x][y]);
  if (x != m + 1) {
    printf("%d ", y);
  }
}

int main() {
  scanf("%d %d", &n, &m);
  for (int i = 0; i < n; i++) {
    int x;
    scanf("%d", &x);
    pref[i + 1] = pref[i] + x;
  }
  fill(dp + 1, dp + n + 1, -inf);
  for (int i = 0; i < m + 1; i++) {
    solve(i + 1, 0, n, 0, n);
    copy(new_dp, new_dp + n + 1, dp);
  }
  printf("%lld\n", dp[n]);
  print(m + 1, n);
  printf("\n");
  return 0;
}

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:48:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &n, &m);
   ~~~~~^~~~~~~~~~~~~~~~~
sequence.cpp:51:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &x);
     ~~~~~^~~~~~~~~~

• Subtask 1: 11 / 11
• Subtask 2: 11 / 11
• Subtask 3: 11 / 11
• Subtask 4: 17 / 17
• Subtask 5: 21 / 21
• Subtask 6: 29 / 29