| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 963054 | RaresFelix | 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>
//#pragma GCC optimize("O3")
//#pragma GCC target("avx,avx2,fma")
#define sz(x) int((x).size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
using namespace std;
using ll = long long;
using ld = long double; // or double, if TL is tight
using str = string;
using ii = pair<int, int>;
using pl = pair<ll, ll>;
using vi = vector<int>;
using vll = vector<ll>;
const ll INF = 1e18;
struct CHT {
int p = 0;
vector<pair<ll, ll> > V;
void insert(ll a, ll b) { /// ax + b
//a va scadea mereu
while(V.size() > 1) {
auto [a1, b1] = V.end()[-1];
auto [a2, b2] = V.end()[-2];
if((b2 - b) * (a1 - a2) <= (b2 - b1) * (a - a2))
V.pop_back();
else break;
}
V.push_back({a, b});
}
ll query(ll x) {
if(V.empty()) return INF;
ll re = INF;
for(auto [a, b] : V)
re = min(a * x + b);
return re;
auto eval = [&](int i) {
return V[i].first * x + V[i].second;
};
while(p + 1 < V.size() && eval(p + 1) <= eval(p)) ++p;
return eval(p);
}
};
int main() {
cin.tie(0);
ios_base::sync_with_stdio(0);
int n, k;
cin >> n >> k;
string s0, s;
cin >> s0;
ll re0 = 0;
int nrB = 0, sum = 0;
for(auto it : s0) {
if(it == 'A') {
++sum;
s += 'A';
re0 += nrB;
if(nrB && sum) {
s += 'B';
--nrB;
--sum;
}
} else {
if(sum) {
s += 'B';
--sum;
} else {
++nrB;
}
}
}
vll A, P(n + 1);
vll SA;
P[0] = -1;
for(auto it : s) {
if(it == 'A'){
A.push_back(nrB);
if(SA.empty())
SA.push_back(A.back());
else
SA.push_back(A.back() + SA.back());
}
else {
++nrB;
P[nrB] = (int)A.size() - 1;
}
}
vll SAP(n);
for(int i = 0; i < n; ++i) {
SAP[i] = 0;
if(P[i] != -1) SAP[i] = SA[P[i]];
}
auto cost = [&](ll st, ll dr) {
return st * P[st] - SAP[st] + SA[dr] - st * dr;
};
vector<vll> DP(n, vll(k + 1, INF));
vector<CHT> Sol(k + 1);
for(int i = 0; i < n; ++i) {
DP[i][1] = cost(0, i);
if(i)
Sol[1].insert(-i, i * P[i] - SAP[i] + DP[i - 1][1]);
for(int j = 2; j <= k; ++j) {
if(i)
Sol[j].insert(-i, DP[i - 1][j] + i * P[i] - SAP[i]);
DP[i][j] = Sol[j - 1].query(i) + SA[i];
}
}
ll re = INF;
for(auto it : DP[n - 1]) re = min(re, it);
cout << re + re0 << "\n";
return 0;
}