Submission #961891

#	Time	Username	Problem	Language	Result	Execution time	Memory
961891		RaresFelix	Chorus (JOI23_chorus)	C++17	0 / 100	1 ms	500 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>;


signed main() {
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    int n, k;
    string s;
    cin >> n >> k >> s;
    int nrB = 0;
    vi A;
    for(int i = 0; i < 2 * n; ++i) {
        if(s[i] == 'B') ++nrB;
        else A.push_back(nrB);
    }
    const int INF = 1e9;
    vector<vi> Cost(n, vi(n, 0));
    for(int i = 0; i < n; ++i) {
        for(int j = i; j < n; ++j) {
            Cost[i][j] = max(0ll, A[j] - i);
            if(j) Cost[i][j] += Cost[i][j - 1];
        }
    }

    auto solve = [&](ld lambda) {
        vector<ld> DP(n, 0.);
        vi Cnt(n, 0), DPreal(n, 0);
        for(int i = 0; i < n; ++i) {
            ///DP[-1] = 0;
            DP[i] = lambda + Cost[0][i];
            Cnt[i] = 1;
            DPreal[i] = Cost[0][i];

            for(int j = 1; j <= i; ++j) {
                ld vnou = DP[j - 1] + Cost[j][i] + lambda;
                if(vnou < DP[i]) {
                    DP[i] = vnou;
                    Cnt[i] = Cnt[j - 1] + 1;
                    DPreal[i] = DPreal[j - 1] + Cost[j][i];
                }
            }
        }
        return ii{Cnt[n - 1], DPreal[n - 1]};
    };
    int re = 1e9;
    ld st = 0, dr = 1e9, mij;
    ld EPS = 1e-8;
    while(dr - st > EPS) {
        mij = (st + dr) / 2;
        auto [nr, val] = solve(mij);
        if(nr > k) st = mij;
        else {
            dr = mij;
            re = min(re, val);
        }
    }
    cout << re << "\n";
    return 0;
}

Compilation message (stderr)

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

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