Submission #97054

#	Time	Username	Problem	Language	Result	Execution time	Memory
97054		MAMBA	Split the sequence (APIO14_sequence)	C++17	71 / 100	2050 ms	83704 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];

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];
  }

  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]] + (A[j] - A[deq[L]]) * A[deq[L]] <=
                 dp[0][deq[L + 1]] + (A[j] - A[deq[L + 1]]) * A[deq[L + 1]])
        L++;
      upt[j][i] = deq[L];
      dp[1][j] = dp[0][deq[L]] + (A[j] - A[deq[L]]) * A[deq[L]];
      while (L < R) {
        int x = deq[R - 1];
        int y = deq[R];
        int z = j;
        ll gxy = (dp[0][x] - dp[0][y] - B[x] + B[y] + (A[y] - A[x] - 1)) /
                 (A[y] - A[x]);
        ll gyz = (dp[0][y] - dp[0][z] - B[y] + B[z] + (A[z] - A[y] - 1)) /
                 (A[z] - A[y]);
        if (gxy < gyz) break;
        R--;
      }
      deq[++R] = j;
    }
    memcpy(dp[0], dp[1], (n + 1) * sizeof(long long));
  }
  cout << dp[0][n] << 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:79: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