Submission #1188056

#	Time	Username	Problem	Language	Result	Execution time	Memory
1188056		versesrev	Split the sequence (APIO14_sequence)	C++20	0 / 100	0 ms	320 KiB

sequence

#include <iostream>
#include <vector>
#include <limits>
#include <numeric>
#include <algorithm>

int main() {
  int n, k;
  std::cin >> n >> k;
  std::vector<int> xs(n);
  for (int& x : xs) std::cin >> x;
  
  std::vector<long long> sum(n);
  std::partial_sum(xs.begin(), xs.end(), sum.begin());
  
  long long INF = std::numeric_limits<long long>::max();
  std::vector<std::vector<long long>> dp(2, std::vector<long long>(n, INF));
  std::vector<std::vector<int>> back(k+1, std::vector<int>(n, -1));
  for (int i = 0; i < n; ++i) {
    dp[0][i] = sum[i] * sum[i];
    back[0][i] = -1;
  }
  for (int ik = 1, cur = 1; ik <= k; ++ik, cur ^= 1) {
    //for (int i = 0; i < n; ++i) {
    auto go = [&](auto&& self, int il, int ir, int jl, int jr) -> void {
      int i = std::midpoint(il, ir);
      dp[cur][i] = INF;
      for (int j = std::max(ik, jl); j <= jr; ++j) {
        long long r = sum[i] - sum[j-1];
        long long v2 = sum[j-1]*sum[j-1]/ik + r*r;
        if (r*(ik+1) < sum[i] and v2 >= dp[cur][i]) break;
        long long v = dp[cur^1][j-1] + r*r;
        if (dp[cur][i] >= v) {
          dp[cur][i] = v;
          back[ik][i] = j - 1;
        }
      }
      if (il < i) self(self, il, i-1, jl, back[ik][i]);
      if (i < ir) self(self, ir+1, ir, back[ik][i], jr);
    };
    go(go, 0, n-1, 0, n-1);
  }
  std::vector<int> ans;
  for (int p = n - 1, ik = k; ik; --ik) {
    p = back[ik][p];
    ans.push_back(p + 1);
  }
  std::ranges::reverse(ans);
  std::cout << ((sum[n-1] * sum[n-1] - dp[k&1][n-1]) / 2) << "\n";
  for (int v : ans) std::cout << v << " ";
  std::cout << "\n";
}

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