Submission #100492

#	Time	Username	Problem	Language	Result	Execution time	Memory
100492		WLZ	Split the sequence (APIO14_sequence)	C++17	100 / 100	1123 ms	85012 KiB

sequence

#include <bits/stdc++.h>
using namespace std;
 
class convex_hull {
  private:
    vector<long long> a, b;
    vector<int> id;
    int ptr = 0;
 
    int bad(int l1, int l2, long long _a, long long _b) {
      if ((a[l1] == _a) && (b[l1] == _b)) return 1;
      return ((_b - b[l1]) * (a[l1] - a[l2]) > (b[l2] - b[l1]) * (a[l1] - _a));
    }
  public:
    void add(long long _a, long long _b, int _id) {
      while ((int) a.size() >= 2 && bad((int) a.size() - 1, (int) a.size() - 2, _a, _b)) {
        a.pop_back();
        b.pop_back();
        id.pop_back();
      }
      a.push_back(_a);
      b.push_back(_b);
      id.push_back(_id);
    }
 
    pair<int, long long> query(long long x) {
      if (ptr >= (int) a.size()) {
        ptr = (int) a.size() - 1;
      }
      while (ptr < (int) a.size() - 1 && a[ptr + 1] * x + b[ptr + 1] >= a[ptr] * x + b[ptr]) {
        ptr++;
      }
      return {id[ptr], a[ptr] * x + b[ptr]};
    }
};
 
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, k;
  cin >> n >> k;
  vector<long long> pre(n + 1, 0);
  for (int i = 1; i <= n; i++) {
    long long a;
    cin >> a;
    pre[i] = pre[i - 1] + a;
  }
  vector< vector<long long> > dp(2, vector<long long>(n + 1, 0));
  vector< vector<int> > from(k + 1, vector<int>(n + 1, -1));
  for (int t = 1; t <= k; t++) {
    convex_hull v;
    int cur = t % 2;
    for (int i = 1; i <= n; i++) {
      if (i > 1) {
        auto tmp = v.query(pre[i]);
        from[t][i] = tmp.first;
        dp[cur][i] = tmp.second;
      }
      v.add(pre[i], dp[!cur][i] - pre[i] * pre[i], i);
    }
  }
  cout << dp[k % 2][n] << '\n';
  int cur = from[k][n], cnt = 1;
  vector<int> ans;
  while (cur != -1) {
    ans.push_back(cur);
    cur = from[k - cnt++][cur];
  }
  reverse(ans.begin(), ans.end());
  for (auto& x : ans) {
    cout << x << ' ';
  }
  cout << '\n';
  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