Submission #1066778

#	Time	Username	Problem	Language	Result	Execution time	Memory
1066778		juicy	Chorus (JOI23_chorus)	C++17	0 / 100	1 ms	2516 KiB

chorus

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

const int N = 1e6 + 5;
const long long inf = 1e18;

struct line {
  long long a, b;

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

  long long div(long long a, long long b) const {
    return a / b - ((a ^ b) < 0 && a % b);
  }

  long long slope(const line &o) const {
    return div(o.b - b, a - o.a);
  }
};

int n, k;
int a[N];
long long pf[N];
string s;
deque<line> hull;
pair<long long, int> dp[N];

void add(line x) {
  while (hull.size() > 2 && hull.end()[-2].slope(hull.back()) <= hull.back().slope(x)) {
    hull.pop_back();
  }
  hull.push_back(x);
}

pair<long long, int> qry(long long x) {
  while (hull.size() > 1 && hull[1].eval(x) < hull[0].eval(x)) {
    hull.pop_front();
  }
  int j = hull[0].a;
  return {hull[0].eval(x), dp[j].second + 1};
}

pair<long long, int> check(long long pen) {
  hull.clear();
  fill(dp, dp + n + 1, pair<long long, int>{inf, 0});
  dp[0] = {0, 0};
  deque<int> dq{0};
  for (int i = 1, j = 0; i <= n; ++i) {
    while (j < i && a[j + 1] <= i) {
      add({j, dp[j].first + pf[j]});
      if (dq.size() && dq.front() == j) {
        dq.pop_front();
      }
      ++j;
    }
    if (dq.size()) {
      dp[i] = dp[dq.front()];
      dp[i].second += 1;
    }
    if (hull.size()) {
      auto x = qry(-i);
      dp[i] = min(dp[i], {x.first + (long long) j * i - pf[j], x.second});
    }
    dp[i].first += pen;
    while (dq.size() && dp[i] <= dp[dq.back()]) {
      dq.pop_back();
    }
    dq.push_back(i);
  }
  return dp[n];
} 

int main() {
  ios::sync_with_stdio(false); cin.tie(nullptr);

  cin >> n >> k >> s;
  for (int i = 0, p = 1; i < 2 * n; ++i) {
    if (s[i] == 'A') {
      ++a[p];
    } else {
      a[p + 1] = a[p];
      ++p;
    }
  }
  for (int i = 1; i <= n; ++i) {
    pf[i] = pf[i - 1] + a[i];
  }
  long long l = 0, r = (long long) n * n, p = r;
  while (l <= r) {
    auto md = (l + r) / 2;
    if (check(md).second <= k) {
      p = md;
      r = md - 1;
    } else {
      l = md + 1;
    }
  }
  cout << check(p).first - k * p;
  return 0;
}

• Subtask 1: 0 / 16
• Subtask 2: 0 / 24
• Subtask 3: 0 / 21
• Subtask 4: 0 / 26
• Subtask 5: 0 / 13