oj.uz

Submission #950751

# Submission time Handle Problem Language Result Execution time Memory
950751 2024-03-20T16:08:56 Z vjudge1 Chorus (JOI23_chorus) C++17
16 / 100
 5 ms 2652 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>;

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;
}

Compilation message

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

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 600 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 600 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 1 ms 604 KB Output is correct
18 Incorrect 5 ms 2652 KB Output isn't correct
19 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 600 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 1 ms 604 KB Output is correct
18 Incorrect 5 ms 2652 KB Output isn't correct
19 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 600 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 1 ms 604 KB Output is correct
18 Incorrect 5 ms 2652 KB Output isn't correct
19 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 600 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 1 ms 604 KB Output is correct
18 Incorrect 5 ms 2652 KB Output isn't correct
19 Halted 0 ms 0 KB -