답안 #950751

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
950751	2024-03-20T16:08:56 Z	vjudge1	Chorus (JOI23_chorus)	C++17	16 / 100	5 ms	2652 KB

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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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	-

답안 #950751

Compilation message

Subtask #1 16.0 / 16.0

Subtask #2 0 / 24.0

Subtask #3 0 / 21.0

Subtask #4 0 / 26.0

Subtask #5 0 / 13.0

Subtask #1
16.0 / 16.0

Subtask #2
0 / 24.0

Subtask #3
0 / 21.0

Subtask #4
0 / 26.0

Subtask #5
0 / 13.0