Submission #931755

#	Time	Username	Problem	Language	Result	Execution time	Memory
931755		alextodoran	Chorus (JOI23_chorus)	C++17	40 / 100	279 ms	101800 KiB

chorus

/**
 _  _   __  _ _ _  _  _ _
 |a  ||t  ||o    d | |o  |
| __    _| | _ | __|  _ |
| __ |/_  | __  /__\ / _\|

**/

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N_MAX = 5000;
const int INF = INT_MAX / 2;

int N, K;
int A[N_MAX + 2];

int dp[N_MAX + 2][N_MAX + 2];
int cost[N_MAX + 2];
int best[N_MAX + 2];

deque <int> rel[N_MAX + 2];

int f (int j, int k) {
    return dp[j][k] + cost[j + 1];
}

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> N >> K;
    string S;
    cin >> S;
    for (int i = 0, j = 0; i < N * 2; i++) {
        if (S[i] == 'A') {
            A[++j] = i + 1;
        }
    }
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= i; j++) {
            cost[j] += max(0, (A[i] - i) - (j - 1));
        }
        dp[i][0] = INF;
        for (int k = 1; k <= K; k++) {
            while (rel[k - 1].empty() == false && f(i - 1, k - 1) <= f(rel[k - 1].back(), k - 1)) {
                rel[k - 1].pop_back();
            }
            rel[k - 1].push_back(i - 1);
            while ((int) rel[k - 1].size() >= 2 && f(rel[k - 1][0], k - 1) >= f(rel[k - 1][1], k - 1)) {
                rel[k - 1].pop_front();
            }
            if (rel[k - 1].empty() == true) {
                dp[i][k] = INF;
            } else {
                dp[i][k] = f(rel[k - 1].front(), k - 1);
            }
        }
    }
    cout << dp[N][K] << "\n";

    return 0;
}

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