oj.uz

Submission #950711

# Submission time Handle Problem Language Result Execution time Memory
950711 2024-03-20T15:34:19 Z vjudge1 Chorus (JOI23_chorus) C++17
0 / 100
 0 ms 348 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);
    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 i = 0; i < n; ++i) {
        AIB Sol(2 * n);
        for(int j = i; j < n; ++j) {
            Sol.update(B[j], 1);
            int re = 0;
            for(int w = i; w <= j; ++w)
                Cost[i][j] += Sol.query(A[w]);
        }
    }
    const int INF = 1e12;
    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 = 0; j < n; ++j) {
            for(int w = 0; w < j; ++w) {
                DP[i][j] = min(DP[i][j], DP[i - 1][w] + Cost[w + 1][j]);
            }
        }
    }
    cout << DP.back()[n - 1] << "\n";
    return 0;
}

Compilation message

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

Subtask #1
0 / 16.0

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

Subtask #2
0 / 24.0

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

Subtask #3
0 / 21.0

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

Subtask #4
0 / 26.0

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

Subtask #5
0 / 13.0

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