답안 #1094825

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1094825	2024-09-30T16:01:14 Z	_8_8_	Chorus (JOI23_chorus)	C++17	61 / 100	2414 ms	117772 KB

chorus

#include <bits/stdc++.h>
    
using namespace std;
    
typedef long long ll;
const int  N = 5e3 + 12, MOD = (int)1e9 + 7;
 
int n, k, x[N], y[N], pref[ 2 * N], col[N], opt[N];
ll dp[N], c[N][N], add = 0;

void make(string &s) {
    string t;
    deque<int> bf;
    int bal = 0;
    for(int i = 0; i < n + n; i++) {
        if(s[i] == 'A') {
            bal++;
            t += 'A';
            if(!bf.empty()) {
                int j = bf[0];
                add += (int)bf.size();
                t += 'B';
                bal--;
                bf.pop_front();
            }
        } else {
            if(bal) {
                bal--;
                t += 'B';
            } else {
                bf.push_back(i);
            }
        }
    }
    s = t;
}
void prec() {
    for(int i = 1; i <= n; i++) {
        for(int j = i; j >= 1; j--) {
            c[j][i] = c[j + 1][i];
            if(y[j] <= x[i]) {
                c[j][i] += pref[x[i]] - pref[y[j] - 1];;
            }
        }
    }
    for(int i = 1; i < n; i++) {
        for(int j = 1; j < n; j++) {
            assert(c[i][j + 1] + c[i + 1][j] >= c[i][j] + c[i + 1][j + 1]);
        }
    }
}
pair<ll, ll> calc_slow(ll pen) {
    for(int i = 1; i <= n; i++) {
        dp[i] = 1e18;
        col[i] = n + 1;
        for(int j = i; j >= 1; j--) {   
            if(pref[y[j]] > pref[x[i]] ) continue;
            if(dp[j - 1] + c[j][i] + pen <= dp[i]) {
                dp[i] = dp[j - 1] + c[j][i] + pen;
                col[i] = col[j - 1] + 1;
                opt[i] = j;
            }
        }
    }
    return {dp[n], col[n]};
}
void test() {
    cin >> n >> k;
    int _x = 0, _y = 0;
    string s;
    cin >> s;
    make(s);
    for(int i = 1; i <= n + n; i++) {
        char a = s[i - 1];
        pref[i] = pref[i - 1];
        if(a == 'A') {
            x[++_x] = i;
            pref[i]++;
        } else { 
            y[++_y] = i;
        }
    }
    prec();
    ll l = -1, r = 1e12, res;
    while(r - l > 1) { 
        ll mid = (l + r) / 2;
        auto [val, t] = calc_slow(mid);
        if(t <= k) {
            r = mid;
            res = val - k * 1ll * mid;
        } else {
            l = mid;
        }
    }
    cout << res + add << '\n';
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); 
    
    int t = 1; 
    // cin >> t;
    
    while(t--) 
        test();
    return 0;
}

Compilation message

chorus.cpp: In function 'void make(std::string&)':
chorus.cpp:20:21: warning: unused variable 'j' [-Wunused-variable]
   20 |                 int j = bf[0];
      |                     ^
chorus.cpp: In function 'void test()':
chorus.cpp:95:19: warning: 'res' may be used uninitialized in this function [-Wmaybe-uninitialized]
   95 |     cout << res + add << '\n';
      |                   ^~~

Subtask #1

16.0 / 16.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Correct	0 ms	468 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 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	1 ms	348 KB	Output is correct
11	Correct	1 ms	604 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

24.0 / 24.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Correct	0 ms	468 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 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	1 ms	348 KB	Output is correct
11	Correct	1 ms	604 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	2 ms	1112 KB	Output is correct
18	Correct	9 ms	3532 KB	Output is correct
19	Correct	9 ms	3420 KB	Output is correct
20	Correct	9 ms	3536 KB	Output is correct
21	Correct	9 ms	3528 KB	Output is correct
22	Correct	9 ms	3420 KB	Output is correct
23	Correct	11 ms	3512 KB	Output is correct
24	Correct	9 ms	3416 KB	Output is correct
25	Correct	8 ms	3420 KB	Output is correct
26	Correct	9 ms	3420 KB	Output is correct
27	Correct	9 ms	3420 KB	Output is correct
28	Correct	10 ms	3512 KB	Output is correct

Subtask #3

21.0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Correct	0 ms	468 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 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	1 ms	348 KB	Output is correct
11	Correct	1 ms	604 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	2 ms	1112 KB	Output is correct
18	Correct	9 ms	3532 KB	Output is correct
19	Correct	9 ms	3420 KB	Output is correct
20	Correct	9 ms	3536 KB	Output is correct
21	Correct	9 ms	3528 KB	Output is correct
22	Correct	9 ms	3420 KB	Output is correct
23	Correct	11 ms	3512 KB	Output is correct
24	Correct	9 ms	3416 KB	Output is correct
25	Correct	8 ms	3420 KB	Output is correct
26	Correct	9 ms	3420 KB	Output is correct
27	Correct	9 ms	3420 KB	Output is correct
28	Correct	10 ms	3512 KB	Output is correct
29	Correct	2254 ms	114468 KB	Output is correct
30	Correct	2171 ms	117744 KB	Output is correct
31	Correct	2220 ms	117588 KB	Output is correct
32	Correct	2325 ms	117768 KB	Output is correct
33	Correct	2370 ms	117584 KB	Output is correct
34	Correct	2289 ms	117772 KB	Output is correct
35	Correct	2314 ms	117768 KB	Output is correct
36	Correct	2293 ms	117744 KB	Output is correct
37	Correct	2301 ms	117744 KB	Output is correct
38	Correct	2414 ms	117620 KB	Output is correct
39	Correct	2231 ms	117748 KB	Output is correct
40	Correct	2227 ms	117384 KB	Output is correct
41	Correct	2305 ms	117536 KB	Output is correct
42	Correct	1027 ms	117588 KB	Output is correct

Subtask #4

0 / 26.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Correct	0 ms	468 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 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	1 ms	348 KB	Output is correct
11	Correct	1 ms	604 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	2 ms	1112 KB	Output is correct
18	Correct	9 ms	3532 KB	Output is correct
19	Correct	9 ms	3420 KB	Output is correct
20	Correct	9 ms	3536 KB	Output is correct
21	Correct	9 ms	3528 KB	Output is correct
22	Correct	9 ms	3420 KB	Output is correct
23	Correct	11 ms	3512 KB	Output is correct
24	Correct	9 ms	3416 KB	Output is correct
25	Correct	8 ms	3420 KB	Output is correct
26	Correct	9 ms	3420 KB	Output is correct
27	Correct	9 ms	3420 KB	Output is correct
28	Correct	10 ms	3512 KB	Output is correct
29	Correct	2254 ms	114468 KB	Output is correct
30	Correct	2171 ms	117744 KB	Output is correct
31	Correct	2220 ms	117588 KB	Output is correct
32	Correct	2325 ms	117768 KB	Output is correct
33	Correct	2370 ms	117584 KB	Output is correct
34	Correct	2289 ms	117772 KB	Output is correct
35	Correct	2314 ms	117768 KB	Output is correct
36	Correct	2293 ms	117744 KB	Output is correct
37	Correct	2301 ms	117744 KB	Output is correct
38	Correct	2414 ms	117620 KB	Output is correct
39	Correct	2231 ms	117748 KB	Output is correct
40	Correct	2227 ms	117384 KB	Output is correct
41	Correct	2305 ms	117536 KB	Output is correct
42	Correct	1027 ms	117588 KB	Output is correct
43	Runtime error	5 ms	1576 KB	Execution killed with signal 11
44	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	468 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 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	1 ms	348 KB	Output is correct
11	Correct	1 ms	604 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	2 ms	1112 KB	Output is correct
18	Correct	9 ms	3532 KB	Output is correct
19	Correct	9 ms	3420 KB	Output is correct
20	Correct	9 ms	3536 KB	Output is correct
21	Correct	9 ms	3528 KB	Output is correct
22	Correct	9 ms	3420 KB	Output is correct
23	Correct	11 ms	3512 KB	Output is correct
24	Correct	9 ms	3416 KB	Output is correct
25	Correct	8 ms	3420 KB	Output is correct
26	Correct	9 ms	3420 KB	Output is correct
27	Correct	9 ms	3420 KB	Output is correct
28	Correct	10 ms	3512 KB	Output is correct
29	Correct	2254 ms	114468 KB	Output is correct
30	Correct	2171 ms	117744 KB	Output is correct
31	Correct	2220 ms	117588 KB	Output is correct
32	Correct	2325 ms	117768 KB	Output is correct
33	Correct	2370 ms	117584 KB	Output is correct
34	Correct	2289 ms	117772 KB	Output is correct
35	Correct	2314 ms	117768 KB	Output is correct
36	Correct	2293 ms	117744 KB	Output is correct
37	Correct	2301 ms	117744 KB	Output is correct
38	Correct	2414 ms	117620 KB	Output is correct
39	Correct	2231 ms	117748 KB	Output is correct
40	Correct	2227 ms	117384 KB	Output is correct
41	Correct	2305 ms	117536 KB	Output is correct
42	Correct	1027 ms	117588 KB	Output is correct
43	Runtime error	5 ms	1576 KB	Execution killed with signal 11
44	Halted	0 ms	0 KB	-