| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 938529 | Ice_man | Chorus (JOI23_chorus) | C++14 | 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 <iostream>
#include <chrono>
#define maxn 10005
#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;
}
long long n, k;
string s;
void read()
{
cin >> n >> k;
cin >> s;
n *= 2;
s = ' ' + s;
}
long long pref[2][maxn][maxn];
long long pom[maxn];
void math()
{
for(long long i = 1; i <= n; i++)
{
if(s[i] == 'A')
pom[i] = 1;
else
pom[i] = -1;
pom[i] += pom[i - 1];
}
for(long long i = 0; i < n / 2 + 1; i++)
for(long long 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];
}
}
long long dp[maxn][maxn], a[maxn];
long long bra, brb;
long long calc(long long l, long long r)
{
if((r - l + 1) % 2 == 1)
return INF;
long long ret = 0;
long long len = r - l + 1;
long long 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;
/**long long ret = 0;
for(long long i = y + 1; i <= x; i++)
if(a[i] >= y)
ret += a[i] - y;
return ret;*/
}
long long dp2[maxn][maxn];
void divide(long long ansl, long long ansr, long long l, long long r, long long son)
{
if(l > r)
return;
long long pos = l + r;
if((l + r) % 2 == 1)
pos--;
///cout << pos << endl;
dp2[pos][son] = ansr;
dp[pos][son] = INF;
for(long long 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;
}
long long mid = pos / 2;
divide(ansl, dp2[pos][son], l, mid - 1, son);
divide(dp2[pos][son], ansr, mid + 1, r, son);
}
long long ans = INF;
void solve()
{
ans = INF;
for(long long i = 1; i <= n; i++)
dp[i][0] = INF;
for(long long 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(long long i = 0; i < 2 * n; i++)
cout << a[i] << " ";
cout << endl;
cout << bra << " " << brb << endl;*/
/**for(long long i = 0; i <= k; i++)
for(long long j = 0; j <= n; j++)
dp[i][j] = INF;
dp[0][0] = 0;
for(long long i = 1; i <= k; i++)
for(long long j = 1; j <= n; j++)
for(long long _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;
}