| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 938530 | 2024-03-05T09:01:24 Z | Ice_man | Chorus (JOI23_chorus) | C++14 | 0 ms | 0 KB |
#include <iostream>
#include <chrono>
#define maxn 10001
#define maxlog 20
#define INF 1000000010
#define LINF 1000000000000000005
#define endl '\n'
#define pb(x) push_back(x)
#define X first
#define Y second
#define control cout<<"passed"<<endl;
#pragma GCC optimize("O3" , "Ofast" , "unroll-loops" , "fast-math")
#pragma GCC target("avx2")
using namespace std;
std::chrono::high_resolution_clock::time_point startT, currT;
constexpr double TIME_MULT = 1;
double timePassed()
{
using namespace std::chrono;
currT = high_resolution_clock::now();
double time = duration_cast<duration<double>>(currT - startT).count();
return time * TIME_MULT;
}
int n, k;
string s;
void read()
{
cin >> n >> k;
cin >> s;
n *= 2;
s = ' ' + s;
}
int pref[2][maxn][maxn];
int pom[maxn];
void math()
{
for(int i = 1; i <= n; i++)
{
if(s[i] == 'A')
pom[i] = 1;
else
pom[i] = -1;
pom[i] += pom[i - 1];
}
for(int i = 0; i < n / 2 + 1; i++)
for(int j = 1; j <= n; j++)
{
pref[0][i][j] = pref[1][i][j] = max(0LL , i - pom[j]);
if(i == 0)
continue;
pref[0][i][j] += pref[0][i - 1][j - 1];
pref[1][i][j] += pref[1][i - 1][j + 1];
}
}
int dp[maxn][maxn], a[maxn];
int bra, brb;
int calc(int l, int r)
{
if((r - l + 1) % 2 == 1)
return INF;
int ret = 0;
int len = r - l + 1;
int mid = (l + r) / 2;
ret += pref[0][len / 2][mid];
ret -= pref[0][0][mid - len / 2];
ret += pref[1][len / 2 - 1][mid + 1];
ret /= 2;
return ret;
/**int ret = 0;
for(int i = y + 1; i <= x; i++)
if(a[i] >= y)
ret += a[i] - y;
return ret;*/
}
int dp2[maxn][maxn];
void divide(int ansl, int ansr, int l, int r, int son)
{
if(l > r)
return;
int pos = l + r;
if((l + r) % 2 == 1)
pos--;
///cout << pos << endl;
dp2[pos][son] = ansr;
dp[pos][son] = INF;
for(int i = min(ansr , pos); i >= ansl; i--)
if(dp[pos][son] > dp[i - 1][son - 1] + calc(i, pos))
{
dp[pos][son] = dp[i - 1][son - 1] + calc(i, pos);
dp2[pos][son] = i;
}
int mid = pos / 2;
divide(ansl, dp2[pos][son], l, mid - 1, son);
divide(dp2[pos][son], ansr, mid + 1, r, son);
}
int ans = INF;
void solve()
{
ans = INF;
for(int i = 1; i <= n; i++)
dp[i][0] = INF;
for(int i = 1; i <= k; i++)
{
divide(1, n, 1, n / 2, i);
ans = min(ans, dp[n][i]);
}
cout << ans << endl;
}
/**void calc_dp()
{
bra = 0;
brb = 0;
for(char c : s)
if(c == 'A')
{
bra++;
a[bra] = brb;
}
else
brb++;
*/
/**for(int i = 0; i < 2 * n; i++)
cout << a[i] << " ";
cout << endl;
cout << bra << " " << brb << endl;*/
/**for(int i = 0; i <= k; i++)
for(int j = 0; j <= n; j++)
dp[i][j] = INF;
dp[0][0] = 0;
for(int i = 1; i <= k; i++)
for(int j = 1; j <= n; j++)
for(int _k = 0; _k < j; _k++)
{
///cout << calc(_k , j) << endl;
dp[i][j] = min(dp[i][j] , dp[i - 1][_k] + calc(_k , j));
}
cout << dp[k][n] << endl;
}*/
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
startT = std::chrono::high_resolution_clock::now();
read();
math();
solve();
return 0;
}