Submission #531632

#	Time	Username	Problem	Language	Result	Execution time	Memory
531632		erke	Split the sequence (APIO14_sequence)	C++11	50 / 100	297 ms	131076 KiB

sequence

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

typedef long long ll;
typedef vector<ll> vl;

const ll oo = 3e18;

int n, k;
vector<ll> comp;

template <typename T>
bool chmax(T &a, T b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
}

namespace sub_1_2_3_4 {
  void solve() {
    vector<ll> a(n + 5), s(n + 5);
    for (int i = 1; i <= n; i++) {
      cin >> a[i];
      s[i] = a[i] + s[i - 1];
    }
    vector<vl> dp(n + 5, vl(k + 5, -oo)), trace(n + 5, vl(k + 5));
    for (int i = 1; i <= n; i++) {
      dp[i][0] = 0;
      for (int l = 1; l <= k; l++)
      for (int j = 1; j <= i - 1; j++) {
        if (chmax(dp[i][l], dp[j][l - 1] + (s[i] - s[j]) * s[j])) {
          trace[i][l] = j;
        }
      }
    }
    cout << dp[n][k] << '\n';
    for (int i = n, j = k; j >= 1; j--) {
      i = trace[i][j];
      cout << i << ' ';
    }
    cout << '\n';
  }
}

struct Line {
  ll a, b, id;
  Line() { a = 0; b = -oo; id = -1; }
  Line(ll _a, ll _b, ll _id): a(_a), b(_b), id(_id) {}
  ll operator()(ll x) { return a * x + b; }
};

struct Node {
  Line line;
  Node *left, *right;
  Node() { left = right = nullptr; }
};

struct LCT {
  Node *root;
  LCT() { root = new Node; }
  void update(Node* &node, ll l, ll r, Line line) {
    if (l > r) return;
    if (node == nullptr) node = new Node;
    if (l == r) {
      if (line(comp[l]) > node->line(comp[l])) node->line = line;
      return;
    }
    ll m = (l + r) / 2;
    if (line.a < node->line.a) swap(line, node->line);
    if (line(comp[m]) > node->line(comp[m])) {
      swap(line, node->line);
      update(node->left, l, m, line);
    }
    else update(node->right, m + 1, r, line);
  }
  pair<ll,ll> get(Node* &node, ll l, ll r, ll x) {
    if (l > r || node == nullptr) return {-oo, -1};
    pair<ll,ll> cur = {node->line(x), node->line.id};
    if (l == r) return cur;
    ll m = (l + r) / 2;
    if (x < comp[m]) return max(cur, get(node->left, l, m, x));
    else return max(cur, get(node->right, m + 1, r, x));
  }
  void update(Line line) {
    update(root, 0, (int) comp.size() - 1, line);
  }
  pair<ll,ll> get(ll x) {
    return get(root, 0, (int) comp.size() - 1, x);
  }
};

namespace sub_5_6 {
  void solve() {
    vector<ll> a(n + 5), s(n + 5);
    for (int i = 1; i <= n; i++) {
      cin >> a[i];
      s[i] = a[i] + s[i - 1];
      comp.push_back(s[i]);
    }
    sort(comp.begin(), comp.end());
    comp.resize(unique(comp.begin(), comp.end()) - comp.begin());
    vector<LCT> lct(k + 5);
    vector<vector<pair<ll,ll>>> dp(n + 5, vector<pair<ll,ll>>(k + 5));
    for (int i = 1; i <= n; i++)
    for (int l = k; l >= 0; l--) {
      if (l >= 1) dp[i][l] = lct[l - 1].get(s[i]);
      lct[l].update(Line(s[i], - (s[i] * s[i]) + dp[i][l].first, i));
    }
    cout << dp[n][k].first << '\n';
    for (int i = n, j = k; j >= 1; j--) {
      i = dp[i][j].second;
      cout << i << ' ';
    }
    cout << '\n';
  }
}

int main() {
  cin.tie(0)->sync_with_stdio(0);
  cin >> n >> k;
  if (n <= 1000) sub_1_2_3_4::solve();
  else sub_5_6::solve();
}

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