Submission #903400

#	Time	Username	Problem	Language	Result	Execution time	Memory
903400		CDuong	Chorus (JOI23_chorus)	C++17	40 / 100	72 ms	2396 KiB

chorus

/*
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,fma,bmi,bmi2,sse4.2,popcnt,lzcnt")
*/

#include <bits/stdc++.h>
#define taskname ""
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define i64 long long
#define i128 __int128
#define pb push_back
#define ff first
#define ss second
#define isz(x) (int)x.size()
using namespace std;

const int mxN = 2e5 + 5;
const int mod = 1e9 + 7;
const i64 oo = 1e18;

int n, k;
int pfx[505], dp[505][505], min_swap[505][505];
string s;
vector<int> posA, posB;

int sum_range(int l, int r) {
    if (l > r) return 0;
    return (l + r) * (r - l + 1) / 2;
}

int calcA(int l, int r) {
    if (l > r) return 0;
    return (l == 0 ? pfx[r] : pfx[r] - pfx[l - 1]);
}

void upd(int &val, int nval) {
    val = (val == -1 ? nval : (val < nval ? val : nval));
}

void solve() {
    cin >> n >> k >> s; s = " " + s;
    if (n > 500) return;
    for (int i = 1; i <= 2 * n; ++i) {
        if (s[i] == 'A') posA.emplace_back(i);
        else posB.emplace_back(i);
    }
    partial_sum(all(posA), pfx);
    for (int l = 0; l < n; ++l) {
        for (int r = l; r < n; ++r) {
            int pos = lower_bound(posA.begin() + l, posA.begin() + r + 1, posB[l]) - posA.begin();
            int offset = 0;
            if (pos <= r) offset = count(s.begin() + posB[l], s.begin() + posA[pos], 'A');
            min_swap[l + 1][r + 1] = calcA(pos, r) - sum_range(posB[l] + offset, posB[l] + offset + (r - pos + 1) - 1);
            // cout << l + 1 << " " << r + 1 << " " << min_swap[l + 1][r + 1] << endl;
        }
        // cout << "\n";
    }
    memset(dp, -1, sizeof dp);
    dp[0][0] = 0;
    for (int j = 0; j < k; ++j) {
        for (int i = 0; i < n; ++i) if (dp[i][j] != -1) {
            for (int ni = i + 1; ni <= n; ++ni) {
                upd(dp[ni][j + 1], dp[i][j] + min_swap[i + 1][ni]);
            }
        }
    }
    cout << dp[n][k] << endl;
}

signed main() {

#ifndef CDuongg
    if(fopen(taskname".inp", "r"))
        assert(freopen(taskname".inp", "r", stdin)), assert(freopen(taskname".out", "w", stdout));
#else
    freopen("bai3.inp", "r", stdin);
    freopen("bai3.out", "w", stdout);
    auto start = chrono::high_resolution_clock::now();
#endif

    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1; //cin >> t;
    while(t--) solve();

#ifdef CDuongg
   auto end = chrono::high_resolution_clock::now();
   cout << "\n"; for(int i = 1; i <= 100; ++i) cout << '=';
   cout << "\nExecution time: " << chrono::duration_cast<chrono::milliseconds> (end - start).count() << "[ms]" << endl;
   cout << "Check array size pls sir" << endl;
#endif

}

• Subtask 1: 16 / 16
• Subtask 2: 24 / 24
• Subtask 3: 0 / 21
• Subtask 4: 0 / 26
• Subtask 5: 0 / 13