Submission #100140

#	Time	Username	Problem	Language	Result	Execution time	Memory
100140		WLZ	Split the sequence (APIO14_sequence)	C++17	33 / 100	191 ms	132096 KiB

sequence

#include <bits/stdc++.h>
using namespace std;

class convex_hull {
  private:
    vector<long long> m, b, id;
    int ptr = 0;

    int bad(int l1, int l2, int l3) {
      return ((b[l3] - b[l1]) * (m[l1] - m[l2]) < (b[l2] - b[l1]) * (m[l1] - m[l3]));
    }
  public:
    void add(long long _a, long long _b, int _id) {
      m.push_back(_a);
      b.push_back(_b);
      id.push_back(_id);
      while ((int) m.size() >= 3 && bad((int) m.size() - 3, (int) m.size() - 2, (int) m.size() - 1)) {
        m.erase(prev(prev(m.end())));
        b.erase(prev(prev(b.end())));
        id.erase(prev(prev(id.end())));
      }
    }

    pair<int, long long> query(long long x) {
      if (ptr >= (int) m.size()) {
        ptr = (int) m.size() - 1;
      }
      while (ptr < (int) m.size() - 1 && m[ptr + 1] * x + b[ptr + 1] >= m[ptr] * x + b[ptr]) {
        ptr++;
      }
      return {id[ptr], m[ptr] * x + b[ptr]};
    }
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, k;
  cin >> n >> k;
  vector<long long> a(n + 1);
  vector<long long> pre(n + 1, 0);
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
    pre[i] = pre[i - 1] + a[i];
  }
  vector< vector<long long> > dp(n + 1, vector<long long>(k + 1, 0));
  vector< vector<int> > from(n + 1, vector<int>(k + 1, -1));
  for (int t = 1; t <= k; t++) {
    convex_hull v;
    for (int i = 1; i <= n; i++) {
      if (i > 1) {
        auto tmp = v.query(pre[i]);
        from[i][t] = tmp.first;
        dp[i][t] = tmp.second;
      }
      v.add(pre[i], dp[i][t - 1] - pre[i] * pre[i], i);
    }
  } 
  cout << dp[n][k] << '\n';
  int cur = from[n][k], cnt = 1;
  vector<int> ans;
  while (cur != -1) {
    ans.push_back(cur);
    cur = from[cur][k - cnt++];
  }
  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: 0 / 17
• Subtask 5: 0 / 21
• Subtask 6: 0 / 29