Submission #1298177

#	Time	Username	Problem	Language	Result	Execution time	Memory
1298177		lmquan	Split the sequence (APIO14_sequence)	C++20	100 / 100	622 ms	82704 KiB

sequence

#define taskname ""
#include <bits/stdc++.h>
using namespace std;
const long long kInf = 5000000000000000000;

struct Line {
  long long a, b;
  int c;

  Line(long long _a = 0, long long _b = 0, int _c = 0) : a(_a), b(_b), c(_c) {}

  long long y(long long x) {
    return a * x + b;
  }

  double Intersect(Line other) {
    return (double)(b - other.b) / (double)(other.a - a);
  }
};

struct ConvexHullTrick {
  deque<Line> S;

  void AddLine(Line l) {
    if (!S.empty() && S.back().a == l.a) {
      if (l.b <= S.back().b) {
        return ;
      } else {
        S.pop_back();
      }
    }
    while (S.size() >= 2 && S[S.size() - 2].Intersect(S.back()) >= S.back().Intersect(l)) {
      S.pop_back();
    }

    S.push_back(l);
  }

  pair<long long, int> Query(long long x) {
    while (S.size() >= 2 && S[0].Intersect(S[1]) < x) {
      S.pop_front();
    }

    return {S[0].y(x), S[0].c};
  }
};

int main() {
  if (fopen(taskname".inp", "r")) {
    freopen(taskname".inp", "r", stdin);
    freopen(taskname".out", "w", stdout);
  }
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

  int n, k;
  cin >> n >> k;
  k++;
  vector<int> a(n + 1);
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
  }

  vector<vector<long long>> dp(2, vector<long long>(n + 1, -kInf));
  vector<vector<int>> f(k + 1, vector<int>(n + 1, 0));
  dp[0][0] = 0;

  for (int i = 1; i <= k; i++) {
    fill(dp[i & 1].begin(), dp[i & 1].end(), -kInf);
    ConvexHullTrick cht;
    long long s = 0;
    for (int j = 1; j <= n; j++) {
      cht.AddLine(Line(s, dp[(i & 1) ^ 1][j - 1] - s * s, j - 1));
      s += a[j];
      pair<long long, int> x = cht.Query(s);
      dp[i & 1][j] = x.first, f[i][j] = x.second;
    }
  }

  cout << dp[k & 1][n] << '\n';
  pair<int, int> x = {k - 1, f[k][n]};
  while (x.first > 0) {
    cout << x.second << ' ';
    x = {x.first - 1, f[x.first][x.second]};
  }

  return 0;
}

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:50:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   50 |     freopen(taskname".inp", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
sequence.cpp:51:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   51 |     freopen(taskname".out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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