제출 #950751

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
950751		vjudge1	Chorus (JOI23_chorus)	C++17	16 / 100	5 ms	2652 KiB

chorus

#include <bits/stdc++.h>
//#pragma GCC optimize("O3")
//#pragma GCC target("avx,avx2,fma")

#define sz(x) int((x).size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

using namespace std;
#define int ll
using ll = long long;
using ld = long double;  // or double, if TL is tight
using str = string; 
using ii = pair<int, int>;
using pl = pair<ll, ll>;
using vi = vector<int>;
using vll = vector<ll>;

struct AIB {
    int n;
    vi V;

    AIB(int N) : n(N + 1), V(N + 1, 0) {}

    void update(int p, int v) {
        ++p;
        while(p < n) {
            V[p] += v;
            p += p & -p;
        }
    }
    
    int query(int p) {
        ++p;
        int re = 0;
        while(p) {
            re += V[p];
            p -= p & - p;
        }
        return re;
    }

    int query(int st, int dr) { return query(dr) - query(st - 1); }
};

signed main() {
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    const int INF = 1e12;

    int n, k;
    cin >> n >> k;
    string s;
    cin >> s;
    vi A, B;
    for(int i = 0; i < 2 * n; ++i)
        if(s[i] == 'A') A.push_back(i);
        else B.push_back(i);
    vector<vi> Cost(n, vi(n, 0)); /// (st, dr) costul pt a le cupla
    for(int st = 0; st < n; ++st) {
        AIB S(2 * n);
        for(int i = st; i < n; ++i) {
            S.update(B[i], 1);
        }
        int re = 0;
        for(int dr = st; dr < n; ++dr) {
            re += S.query(A[dr]);
            Cost[st][dr] = re;
        }
    }
    vector<vi> DP(k, vi(n, 1e12));
    for(int i = 0; i < n; ++i)
        DP[0][i] = Cost[0][i];
    for(int i = 1; i < k; ++i) {
        for(int j = i; j < n; ++j) {
            auto cost = [&](int w) {
                return DP[i - 1][w] + Cost[w + 1][j];
            };
            DP[i][j] = min(DP[i][j], cost(j - 1));
            int st = 0, dr = j - 2, mij;
            while (st < dr) {
                mij = (st + dr) / 2;
                int v1 = cost(mij), v2 = cost(mij + 1);

                if (v1 < v2) {
                    dr = mij;
                } else st = mij + 1;

                DP[i][j] = min(DP[i][j], min(v1, v2));
            }
        }
    }
    cout << DP.back()[n - 1] << "\n";
    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

chorus.cpp: In function 'int main()':
chorus.cpp:49:15: warning: unused variable 'INF' [-Wunused-variable]
   49 |     const int INF = 1e12;
      |               ^~~

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