| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 896065 | cadmiumsky | Chorus (JOI23_chorus) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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 = 505;
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;
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';
}