| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 902500 | Tuanlinh123 | Chorus (JOI23_chorus) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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;
}