Submission #898683

#	Time	Username	Problem	Language	Result	Execution time	Memory
898683		NeroZein	Split the sequence (APIO14_sequence)	C++17	0 / 100	190 ms	131072 KiB

sequence

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

#ifdef Nero
#include "Deb.h"
#else
#define deb(...)
#endif

const int K = 202;
const int N = 1e5 + 5;
const int M = 1e9 + 9;

struct Line {
  int m, b, o;
  Line() {}
  Line(int m_, int b_, int o_) : m(m_), b(b_), o(o_) {}
  long long val(int x) {
    return (long long) -m * x + b;
  }
};

int a[N];
int path[N][K];
long long dp[N][K];
int path2[N][K];
long long dp2[N][K];
int pref[N], suf[N];

struct LiChaoTree {
  int n;
  int rt, idd; 
  vector<Line> seg;
  vector<int> L, R;
  LiChaoTree(int n_) : n(n_) {
    idd = 0; 
    seg.resize(n);
    L.resize(n);
    R.resize(n);
  }
  void upd(int& nd, int l, int r, Line line) {
    if (!nd) {
      nd = ++idd; 
      seg[nd] = line;
      return; 
    }
    int mid = (l + r) >> 1;
    bool f1 = line.val(l) > seg[nd].val(l);
    bool f2 = line.val(mid) > seg[nd].val(mid);
    if (f2) {
      swap(seg[nd], line); 
    }
    if (l == r) {
      return; 
    }
    if (f1 != f2) {
      upd(L[nd], l, mid, line);
    } else {
      upd(R[nd], mid + 1, r, line); 
    }
  }
  void upd(Line line) {
    upd(rt, 0, M, line); 
  }
  pair<long long, int> qry(int nd, int l, int r, int x) {
    if (!nd) {
      return make_pair(-1e18, 0);
    }
    pair<long long, int> ret = {seg[nd].val(x), seg[nd].o}; 
    if (l == r) {
      return ret; 
    }
    int mid = (l + r) >> 1;
    if (x <= mid) {
      ret = max(ret, qry(L[nd], l, mid, x));
    } else {
      ret = max(ret, qry(R[nd], mid + 1, r, x)); 
    }
    return ret; 
  }
  pair<long long, int> qry(int x) {
    return qry(rt, 0, M, x); 
  }
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int n, k;
  cin >> n >> k;
  for (int i = 1; i <= n; ++i) {
    cin >> a[i];
  }
  for (int i = 1; i <= n; ++i) {
    pref[i] = pref[i - 1] + a[i];
  }
  for (int i = n; i >= 1; --i) {
    suf[i] = suf[i + 1] + a[i];
  }
  int ind = 0; 
  long long ans = 0; 
  for (int i = 1; i <= n; ++i) {
    dp[i][k - 1] = (long long) pref[i] * suf[i + 1];
    dp2[i][k - 1] = (long long) pref[i] * suf[i + 1];
    if (k == 1 && dp[i][k - 1] > ans) {
      ans = dp[i][k - 1];
      ind = i; 
    }
  }
  for (int j = k - 2; j >= 0; --j) {
    LiChaoTree st(N); 
    for (int i = k - j; i < n; ++i) {
      {
        long long c = (long long) suf[i + 1] * pref[i];
        for (int l = i - 1; l >= 0; --l) {
          long long cl = dp2[l][j + 1] - (long long) suf[i + 1] * pref[l];
          if (c + cl > dp2[i][j]) {
            dp2[i][j] = c + cl;
            path2[i][j] = l;
          }
          dp2[i][j] = max(dp2[i][j], c + cl);
        }
      }
      st.upd(Line(pref[i - 1], dp[i - 1][j + 1], -(i - 1))); 
      long long c = (long long) suf[i + 1] * pref[i];
      auto [cl, l] = st.qry(suf[i + 1]); 
      dp[i][j] = c + cl;
      assert(dp[i][j] == dp2[i][j]); 
      path[i][j] = -l; 
      if (j == 0 && dp[i][j] > ans) {
        ans = dp[i][j];
        ind = i;
      }
    }
  }
  int cnt = 0;
  vector<int> p;
  while (ind) {
    p.push_back(ind);
    ind = path[ind][cnt++];
  }
  //assert(cnt == k); 
  reverse(p.begin(), p.end()); 
  cout << ans << '\n'; 
  for (int i : p) {
    cout << i << ' ';
  }
  return 0;
}

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