제출 #698200

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
698200		tvladm2009	수열 (APIO14_sequence)	C++17	33 / 100	15 ms	3412 KiB

sequence

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
#define int ll
const int N = (int) 1e5 + 7;
const int K = (int) 2e2 + 7;
int a[N], sp[N], dp[N][K], rec[N][K];

struct Line {
  int a;
  int b;
  int ind;

  int eval(int x) {
    return a * x + b;
  }
};

struct Fraction {
  int num;
  ll den;
};

Fraction x(Line l1, Line l2) {
  // l1.a * x + l1.b = y
  // l2.a * x + l2.b = y

  // l1.a * x + l1.b = l2.a * x + l2.b
  // l1.a * x - l2.b * x = l2.b - l1.b
  // (l1.a - l2.b) * x = l2.b - l1.b

  // x = (l2.b - l1.b) / (l1.a - l2.a)

  if (l1.a - l2.a > 0) {
    return {l2.b - l1.a, l1.a - l2.a};
  } else {
    return {-(l2.b - l1.b), -(l1.a - l2.a)};
  }
}

bool operator <= (const Fraction &a, const Fraction &b) {
  return a.num * b.den <= a.den * b.num;
}

deque<Line> DS;

void add(Line line) {
  while ((int) DS.size() >= 2 && x(DS.end()[-1], line) <= x(DS.end()[-2], DS.end()[-1])) {
    DS.pop_back();
  }
  DS.push_back(line);
}

pair<ll, int> query(int x) {
  while ((int) DS.size() >= 2 && DS[0].eval(x) <= DS[1].eval(x)) {
    DS.pop_front();
  }
  return {DS[0].eval(x), DS[0].ind};
}

void solve(int layer, int n) {
  DS.clear();
  for (int i = layer; i <= n; i++) {
    add({sp[i - 1], dp[layer - 1][i - 1] - sp[i - 1] * sp[i - 1], i - 1});
    pair<int, int> aux = query(sp[i]);
    dp[layer][i] = aux.first;
    rec[layer][i] = aux.second;
  }
}

signed main() {
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

  int n, k;
  cin >> n >> k;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
  }
  for (int i = 1; i <= n; i++) {
    sp[i] = sp[i - 1] + a[i];
    dp[1][i] = 0;
  }
  for (int i = 2; i <= k + 1; i++) {
    solve(i, n);
  }

  cout << dp[k + 1][n] << "\n";
  vector<int> sol;
  int aux = rec[k + 1][n];
  while (k > 0) {
    sol.push_back(aux);
    aux = rec[k][aux];
    k--;
  }
  reverse(sol.begin(), sol.end());
  for (auto &it : sol) {
    cout << it << " ";
  }
  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