oj.uz

Submission #961891

# Submission time Handle Problem Language Result Execution time Memory
961891 2024-04-12T16:57:48 Z RaresFelix Chorus (JOI23_chorus) C++17
0 / 100
 1 ms 500 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 500 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Incorrect 0 ms 344 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 500 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Incorrect 0 ms 344 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 500 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Incorrect 0 ms 344 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 500 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Incorrect 0 ms 344 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 500 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Incorrect 0 ms 344 KB Output isn't correct
7 Halted 0 ms 0 KB -