Submission #896067

#	Time	Username	Problem	Language	Result	Execution time	Memory
896067		cadmiumsky	Chorus (JOI23_chorus)	C++17	61 / 100	341 ms	196780 KiB

chorus

#include <bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
using namespace std;

using ll = long long;
using ld = long double;

//#define int ll
#define sz(x) ((int)(x).size())

using pii = pair<int,int>;
using tii = tuple<int,int,int>;

const int nmax = 5005;
const ll inf = 1e9 + 5;

int B[nmax];

ll dp[nmax][nmax];

ll sum_under[nmax], cnt_under[nmax];
ll sum_pref[nmax];

namespace CHT {
  struct Line {
    ll m, b;
    Line(ll a, ll c): m(a), b(c) {;}
    ll operator()(const ll& x) const { return m * x + b; }
  };
  
  bool bad(Line second, Line last, Line nv) {
    return (nv.b - last.b) * (second.m - nv.m) < (nv.b - second.b) * (last.m - nv.m); 
  }
  
  vector<Line> st;
  int ptr;
  
  void push(Line a) {
    while(sz(st) > 1 && bad(rbegin(st)[1], rbegin(st)[0], a)) st.pop_back();
    st.emplace_back(a);
  }
  
  ll query(int P) {
    ptr = min(ptr, sz(st) - 1);
    while(ptr + 1 < sz(st) && st[ptr](P) > st[ptr + 1](P))
      ptr++;
    return st[ptr](P);
  }
  
  void clear() {
    st.clear();
    ptr = 0;
  }
}

signed main() {
  cin.tie(0) -> sync_with_stdio(0);
  int n, k;
  cin >> n >> k;
  
  int cnt[2] = {0, 0};
  char ch;
  for(int i = 0; i < 2 * n; i++) {
    cin >> ch;
    if(ch == 'A')
      cnt[0]++;
    else
      B[++cnt[1]] = cnt[0];
      //cerr << cnt[0] << '\n';
  }
  
  ll fixing = 0;
  for(int i = 1; i <= n; i++) {
    int target = max(B[i - 1], i);
    fixing += max(0, target - B[i]);
    B[i] += max(0, target - B[i]);
  }
  
  for(int i = 1; i <= n; i++)
    cnt_under[B[i]]++,
    sum_under[B[i]] += B[i],
    sum_pref[i] = sum_pref[i - 1] + B[i];
  
  for(int i = 1; i <= n; i++)
    cnt_under[i] += cnt_under[i - 1],
    sum_under[i] += sum_under[i - 1];
  
  //for(int i = 1; i <= n; i++)
    //cout << B[i] << ' ';
  //cout << '\n';
  
  for(int i = 1; i <= n; i++)
    dp[0][i] = inf;
  dp[0][n + 1] = 0;
  
  for(int dim = 1; dim <= k; dim++) {
    
    int last_nv = n;
    
    CHT::clear();
    
    for(int i = n; i > 0; i--) {
      
      while(last_nv >= B[i]) {
        CHT::push(CHT::Line(last_nv, -sum_under[last_nv] + cnt_under[last_nv] * last_nv + last_nv + dp[dim - 1][last_nv + 1]));
        last_nv--;
      }
      
      dp[dim][i] = CHT::query(-i) + sum_pref[i - 1];
    }
  }
  
  cout << dp[k][1] + fixing << '\n';
  
  
  
  
}

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