Submission #97007

#	Time	Username	Problem	Language	Result	Execution time	Memory
97007		MAMBA	Split the sequence (APIO14_sequence)	C++17	71 / 100	2041 ms	83448 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;
typedef pair<int, int> pii;
typedef complex<long double> point;

template <typename S, typename T>
inline void smin(S &l, T r) {
  l = l < r ? l : r;
}

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 B[r] - B[l - 1] - A[l - 1] * (A[r] - A[l - 1]);
}

void solve(int l, int r, int s, int t, int w) {
  if (l >= r) return;
  int mid = l + r >> 1;
  dp[1][mid] = 2e18;
  int id = s;
  rep(i, s, min(mid, t)) {
    ll val = dp[0][i] + f(i + 1, mid);
    if (val < dp[1][mid]) {
      dp[1][mid] = val;
      id = i;
    }
  }
  upt[mid][w] = id;
  solve(l, mid, s, id + 1, w);
  solve(mid + 1, r, id, t, w);
}

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] = B[i - 1] + a[i] * A[i - 1];
    dp[0][i] = 2e18;
  }

  rep(i, 0, k + 1) {
    solve(1, n + 1, 0, n, i);
    memcpy(dp[0], dp[1], (n + 1) * sizeof(long long));
  }
  cout << B[n] - 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 'void solve(int, int, int, int, int)':
sequence.cpp:34:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int mid = l + r >> 1;
             ~~^~~
sequence.cpp: In function 'int main()':
sequence.cpp:80: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