Submission #97048

#	Time	Username	Problem	Language	Result	Execution time	Memory
97048		MAMBA	Split the sequence (APIO14_sequence)	C++17	71 / 100	2037 ms	83712 KiB

sequence

//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#include <bits/stdc++.h>

using namespace std;

#define rep(i, j, k) for (int i = j; i < k; i++)
#define pb push_back
#define for_all(x) x.begin(), x.end()

constexpr int N = 1e5 + 10;

typedef long long ll;

int n, k;
ll dp[2][N], a[N], A[N], B[N];
int upt[N][202];

inline ll f(int l, int r) { return (A[r] - A[l - 1]) * (A[r] - A[l - 1]); }

inline double g(int x, int y) {
  return A[y] + ((1.0 * dp[0][y] - dp[0][x] - (A[y] - A[x]) * (A[y] - A[x])) /
                 (2 * (A[y] - A[x])));
}

int deq[N], L, R;

bool mark[N];

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);

  cin >> n >> k;
  rep(i, 1, n + 1) {
    cin >> a[i];
    A[i] = A[i - 1] + a[i];
    B[i] = A[i] * A[i];
    dp[0][i] = B[i];
  }

  rep(i, 1, k + 1) {
    L = R = 0;
    deq[R] = 0;
    rep(j, 1, n + 1) {
      if (a[j] == 0) {
        dp[1][j] = dp[1][j - 1];
        upt[j][i] = upt[j - 1][i];
        continue;
      }
      while (L < R && dp[0][deq[L]] + f(deq[L] + 1, j) >=
                          dp[0][deq[L + 1]] + f(deq[L + 1] + 1, j))
        L++;
      upt[j][i] = deq[L];
      dp[1][j] = dp[0][deq[L]] + f(deq[L] + 1, j);
      while (L < R && g(deq[R], j) <= g(deq[R - 1], deq[R])) R--;
      deq[++R] = j;
    }
    memcpy(dp[0], dp[1], (n + 1) * sizeof(long long));
  }
  cout << (B[n] - dp[0][n]) / 2 << endl;
  vector<int> res;
  int me = upt[n][k];
  for (int i = k; i; i--) {
    if (me) {
      res.pb(me);
      mark[me] = true;
    }
    me = upt[me][i - 1];
  }

  int ptr = 1;
  while (res.size() < k) {
    if (!mark[ptr]) res.pb(ptr);
    ptr++;
  }
  for (auto e : res) cout << e << ' ';

  return 0;
}

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:76:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while (res.size() < k) {
          ~~~~~~~~~~~^~~

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