Submission #1059620

#	Time	Username	Problem	Language	Result	Execution time	Memory
1059620		nima_aryan	Split the sequence (APIO14_sequence)	C++17	100 / 100	345 ms	87308 KiB

sequence

/**
 *    author:  NimaAryan
 *    created: 2024-08-15 09:11:58  
**/
#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "algo/debug.h"
#endif

using i64 = long long;

constexpr i64 inf = 1E15;

struct Line {
  i64 a, b;
  int i;

  i64 operator()(int x) const {
    return a * x + b;
  }

  bool intersects_earlier(const Line& A, const Line& B) {
    return (A.b - b) * (a - B.a) <= (B.b - b) * (a - A.a);
  }
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  
  int n, k;
  cin >> n >> k;

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

  vector<i64> s(n + 1);
  for (int i = 0; i < n; ++i) {
    s[i + 1] = s[i] + a[i];
  }

  vector<i64> f(n + 1);
  f[0] = -inf;
  vector to(k + 1, vector<int>(n + 1));
  iota(to[0].begin(), to[0].end(), 0);
  to[0][0] = -1;
  for (int kk = 1; kk <= k; ++kk) {
    vector<i64> g(n + 1);
    vector<Line> f_max(2 * n + 3);
    int l = 0, r = 0;
    for (int i = 0; i <= n; ++i) {
      while (r - l >= 2 && f_max[l](s[i]) < f_max[l + 1](s[i])) {
        ++l;
      }
      if (r - l >= 1) {
        g[i] = f_max[l](s[i]);
        to[kk][i] = f_max[l].i;
      } else {
        g[i] = -inf;
      }
      Line fi = Line{s[i], f[i] - s[i] * s[i], i};
      while (r - l >= 2 && f_max[r - 2].intersects_earlier(fi, f_max[r - 1])) {
        --r;
      }
      f_max[r++] = fi;
    }
    f.swap(g);
  }

  cout << f[n] << "\n";
  vector<int> ans;
  for (int i = n; k >= 0; i = to[k][i], --k) {
    ans.push_back(i);
  }
  for (int i = ans.size() - 1; i >= 1; --i) {
    cout << ans[i] << " ";
  }

  return 0;
}

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