Submission #950846

#	Time	Username	Problem	Language	Result	Execution time	Memory
950846		vjudge1	Chorus (JOI23_chorus)	C++17	0 / 100	1 ms	348 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;
        }
    }
    ld st = 0., dr = 1e9, mij;
    const ld EPS = 1e-12;
    mt19937 rng(1);

    vector<ld> DE(n);
    for(int i = 0; i < n; ++i)
        DE[i] = uniform_real_distribution<ld>(-1e-7, 1e-7)(rng);
    auto check = [&](ld lambda) {
        vi St(n, 0); 
        int st = 0;
        for(int i = 0; i < n; ++i) {
            while(st <= i && lambda - Cost[st][i] + DE[i] < 0) ++st;
            if(st > i) return -1ll;
            St[i] = st;
        }
        vi DP(n, 0), Cnt(n, 0);
        for(int i = 0; i < n; ++i) {
            if(!St[i])  {
                DP[i] = Cost[0][i];
                Cnt[i] = 1;
                continue;
            }
            DP[i] = DP[St[i] - 1] + Cost[St[i]][i];
            Cnt[i] = Cnt[St[i] - 1] + 1;
        }
        if(Cnt.back() > k)
            return -1ll;
        else return DP.back();
    };

    while(dr - st > EPS) {
        mij = (st + dr) / 2;
        if(check(mij) == -1) {
            st = mij;
        } else {
            dr = mij;
        }
    }

    int re = check((st + dr) / 2);
    cout << re << "\n";
    return 0;
}

Compilation message (stderr)

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

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