제출 #255108

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
255108		rama_pang	수열 (APIO14_sequence)	C++14	100 / 100	757 ms	86764 KiB

sequence

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

using lint = long long;
const lint INF = 1e18;
const int MAXN = 1e5 + 5;
const int MAXK = 205;

// Order of operations doesn't matter, the score is always the same.
//
// dp[n][k] = using k operations, how many ways to divide 1...n with maximum score
// dp[n][k] = dp[prv][k-1] + (A[n] - A[prv]) * A[prv]
// dp[n][k] = dp[prv][k-1] + A[n] * A[prv] - A[prv] * A[prv]
// Convex Hull Trick, evaluate x = A[n], y = A[prv] * x + dp[prv][k-1] - A[prv]^2
// A[prv] and A[n] is non decreasing, we can use monotone queue for amortized O(1) insertion and query.
//
// Use flying table on the (int64) DP table, maintaining a separate backtracking table which
// only uses int32 to save memory.
//
// Time Complexity: O(NK)

int N, K;
lint A[MAXN];
lint dp[MAXN][2];
int tr[MAXN][MAXK];

struct Line { // ax + b
  int id;
  lint a, b;
  Line() {}
  Line(int id, lint a, lint b) : id(id), a(a), b(b) {}
  lint get(lint x) { return a * x + b; }
};

class ConvexHull {
 public:
  ConvexHull() {}

  int sz, ptr = 0;
  vector<Line> line;

  bool Majorize(Line a, Line b, Line c) { // Check if Intersection(a, c).x <= Intersection(b, c).x
    // a1x + b1 = a2x + b2
    // x = (b2 - b1) / (a1 - a2)
    if (a.a - c.a == 0 && a.a - b.a == 0) return true;
    if (a.a - c.a == 0) {
      if (c.b - a.b < 0 && a.a - b.a < 0) return false;
      if (c.b - a.b > 0 && a.a - b.a > 0) return false;
      return true;
    }
    if (a.a - b.a == 0) {
      if (c.b - a.b <= 0 && a.a - b.a <= 0) return true;
      if (c.b - a.b >= 0 && a.a - b.a >= 0) return true;
      return false;
    }
    return (1.00 * (c.b - a.b) / (a.a - c.a)) <= (1.00 * (b.b - a.b) / (a.a - b.a));
  } 

  void Insert(Line n) {
    sz = line.size();
    while (ptr + 1 < sz && Majorize(line[sz - 2], line[sz - 1], n)) {
      line.pop_back();
      sz--;
    }
    line.emplace_back(n);
  }

  pair<int, lint> Query(lint x) {
    if (line.empty()) {
      return {-1, -INF};
    }
    sz = line.size();
    while (ptr + 1 < sz && line[ptr].get(x) <= line[ptr + 1].get(x)) {
      ptr++;
    }
    return {line[ptr].id, line[ptr].get(x)};
  }

  void clear() {
    ptr = 0;
    line.clear();
  }
};

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);

  for (int i = 0; i < MAXN; i++) {
    for (int j = 0; j < MAXK; j++) {
      dp[i][j & 1] = -INF;
      tr[i][j] = -1;
    }
  }

  cin >> N >> K;
  for (int i = 1; i <= N; i++) {
    cin >> A[i];
    A[i] += A[i - 1];
  }

  for (int n = 0; n <= N; n++) {
    dp[n][0] = 0;
  }
  ConvexHull ch;
  for (int k = 1; k <= K; k++) {
    ch.clear();
    for (int n = 1; n <= N; n++) {
      auto cost = ch.Query(A[n]);
      dp[n][k & 1] = cost.second;
      tr[n][k] = cost.first;
      ch.Insert(Line(n, A[n], dp[n][(k - 1) & 1] - A[n] * A[n]));
      dp[n][(k - 1) & 1] = -INF;
    }
  }

  vector<int> ans;
  int n = N, k = K;
  while (k > 0) {
    ans.emplace_back(tr[n][k]);
    n = tr[n][k--];
  }
  reverse(begin(ans), end(ans));
  cout << dp[N][K & 1] << "\n";
  for (auto i : ans) {
    cout << i << " ";
  }
  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