#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,fma,bmi,bmi2,popcnt,lzcnt")
#include<bits/stdc++.h>
#define ll long long
#define pll pair<ll, ll>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define ld long double
using namespace std;
const long long inf=1e6, maxn=1e6+5;
ll cnt[maxn], to[maxn];
long long n, k, dp[maxn], pre[maxn];
struct Line
{
long long a=inf, b=inf;
ll idx=0;
Line(){}
Line(long long a, long long b, ll idx): a(a), b(b), idx(idx){}
inline pair<long long, ll> ask(long long x)
{
if (a==inf) return {inf*inf, idx};
return {a*x+b, idx};
}
};
struct Node
{
Line A;
ll l, r;
};
Node LC[maxn*60];
struct Lichao
{
ll crr;
Lichao()
{
crr=0;
LC[0]=Node();
}
inline void addline(Line A)
{
ll Start=-inf, End=inf, i=0;
while (1)
{
ll mid=(Start+End)/2;
bool l=A.ask(Start).fi<LC[i].A.ask(Start).fi;
bool m=A.ask(mid).fi<LC[i].A.ask(mid).fi;
if (m) swap(A, LC[i].A);
if (A.a==inf) break;
if (Start+1!=End)
{
if (l!=m)
{
if (!LC[i].l)
{
LC[i].l=++crr;
LC[crr]=Node();
}
i=LC[i].l;
End=mid;
}
else
{
if (!LC[i].r)
{
LC[i].r=++crr;
LC[crr]=Node();
}
i=LC[i].r;
Start=mid;
}
}
else break;
}
}
inline pair<long long, ll> query(long long x)
{
ll Start=-inf, End=inf, i=0;
pair<long long, ll> ans={inf*inf, 0};
while (1)
{
ll mid=(Start+End)/2;
ans=min(ans, LC[i].A.ask(x));
if (x<mid && LC[i].l)
{
i=LC[i].l;
End=mid;
}
else if (x>=mid && LC[i].r)
{
i=LC[i].r;
Start=mid;
}
else break;
}
return ans;
}
};
pair<long long, ll> solve(long long C)
{
ll crr=1;
Lichao A; A.addline(Line(0, -pre[to[0]-1], 0));
for (ll i=1; i<=n; i++)
dp[i]=inf*inf, cnt[i]=0;
for (ll i=1; i<=n; i++)
{
while (crr<i && to[crr]<=i)
A.addline(Line(-crr, -(pre[to[crr]-1]-(to[crr]-1)*crr)+dp[crr], cnt[crr])), crr++;
tie(dp[i], cnt[i])=A.query(i);
dp[i]+=C+pre[i], cnt[i]++;
if (crr<i && dp[crr]+C<dp[i])
dp[i]=dp[crr]+C, cnt[i]=cnt[crr]+1;
}
return {dp[n], cnt[n]};
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n >> k;
string s; cin >> s;
long long x=0, y=0, crr=1;
for (ll i=0; i<n*2; i++)
{
if (s[i]=='A')
x++, pre[x]=pre[x-1]+y;
else y++;
}
for (ll i=1; i<=n; i++)
while (crr<=pre[i]-pre[i-1])
to[crr]=i, crr++;
while (crr<=n) to[crr]=n+1, crr++;
for (ll i=0; i<=n; i++)
if (to[i]<=i)
to[i]=i+1;
long long lo=0, hi=1LL*n*n;
while (hi>lo)
{
long long mid=(lo+hi)/2;
if (solve(mid).se<=k)
hi=mid;
else lo=mid+1;
}
cout << 0LL+solve(lo).fi-lo*k;
}
Compilation message
/tmp/ccMxlTzf.o: in function `solve(long long)':
chorus.cpp:(.text+0x8): relocation truncated to fit: R_X86_64_PC32 against symbol `pre' defined in .bss section in /tmp/ccMxlTzf.o
chorus.cpp:(.text+0x39): relocation truncated to fit: R_X86_64_PC32 against symbol `to' defined in .bss section in /tmp/ccMxlTzf.o
chorus.cpp:(.text+0x18a): relocation truncated to fit: R_X86_64_PC32 against symbol `n' defined in .bss section in /tmp/ccMxlTzf.o
chorus.cpp:(.text+0x1b4): relocation truncated to fit: R_X86_64_PC32 against symbol `dp' defined in .bss section in /tmp/ccMxlTzf.o
chorus.cpp:(.text+0x2f8): relocation truncated to fit: R_X86_64_PC32 against symbol `dp' defined in .bss section in /tmp/ccMxlTzf.o
chorus.cpp:(.text+0x314): relocation truncated to fit: R_X86_64_PC32 against symbol `dp' defined in .bss section in /tmp/ccMxlTzf.o
chorus.cpp:(.text+0x343): relocation truncated to fit: R_X86_64_PC32 against symbol `cnt' defined in .bss section in /tmp/ccMxlTzf.o
chorus.cpp:(.text+0x36c): relocation truncated to fit: R_X86_64_PC32 against symbol `cnt' defined in .bss section in /tmp/ccMxlTzf.o
chorus.cpp:(.text+0x42b): relocation truncated to fit: R_X86_64_PC32 against symbol `pre' defined in .bss section in /tmp/ccMxlTzf.o
chorus.cpp:(.text+0x4b3): relocation truncated to fit: R_X86_64_PC32 against symbol `to' defined in .bss section in /tmp/ccMxlTzf.o
chorus.cpp:(.text+0x4e8): additional relocation overflows omitted from the output
/usr/bin/ld: failed to convert GOTPCREL relocation; relink with --no-relax
collect2: error: ld returned 1 exit status
