답안 #1094838

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1094838	2024-09-30T16:10:56 Z	_8_8_	Chorus (JOI23_chorus)	C++17	61 / 100	2471 ms	117904 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(pref[x[i]] - pref[min(x[j], y[j]) - 1] != i - j + 1) {
                exit(-1);
            }
            if(y[j] <= x[i]) {
                c[j][i] += pref[x[i]] - pref[y[j] - 1];;
            }
        }
    }
    //monge 
    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(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:98:19: warning: 'res' may be used uninitialized in this function [-Wmaybe-uninitialized]
   98 |     cout << res + add << '\n';
      |                   ^~~

Subtask #1
16.0 / 16.0

#	결과	메모리	Grader output
1	Correct	348 KB	Output is correct
2	Correct	348 KB	Output is correct
3	Correct	348 KB	Output is correct
4	Correct	348 KB	Output is correct
5	Correct	464 KB	Output is correct
6	Correct	348 KB	Output is correct
7	Correct	348 KB	Output is correct
8	Correct	348 KB	Output is correct
9	Correct	348 KB	Output is correct
10	Correct	348 KB	Output is correct
11	Correct	348 KB	Output is correct
12	Correct	348 KB	Output is correct
13	Correct	348 KB	Output is correct
14	Correct	348 KB	Output is correct
15	Correct	348 KB	Output is correct
16	Correct	348 KB	Output is correct

Subtask #2
24.0 / 24.0

#	결과	실행 시간	메모리	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	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	464 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	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	2 ms	1372 KB	Output is correct
18	Correct	8 ms	3528 KB	Output is correct
19	Correct	8 ms	3532 KB	Output is correct
20	Correct	8 ms	3420 KB	Output is correct
21	Correct	7 ms	3420 KB	Output is correct
22	Correct	7 ms	3420 KB	Output is correct
23	Correct	11 ms	3416 KB	Output is correct
24	Correct	7 ms	3420 KB	Output is correct
25	Correct	7 ms	3420 KB	Output is correct
26	Correct	7 ms	3420 KB	Output is correct
27	Correct	7 ms	3420 KB	Output is correct
28	Correct	7 ms	3420 KB	Output is correct

Subtask #3
21.0 / 21.0

#	결과	실행 시간	메모리	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	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	464 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	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	2 ms	1372 KB	Output is correct
18	Correct	8 ms	3528 KB	Output is correct
19	Correct	8 ms	3532 KB	Output is correct
20	Correct	8 ms	3420 KB	Output is correct
21	Correct	7 ms	3420 KB	Output is correct
22	Correct	7 ms	3420 KB	Output is correct
23	Correct	11 ms	3416 KB	Output is correct
24	Correct	7 ms	3420 KB	Output is correct
25	Correct	7 ms	3420 KB	Output is correct
26	Correct	7 ms	3420 KB	Output is correct
27	Correct	7 ms	3420 KB	Output is correct
28	Correct	7 ms	3420 KB	Output is correct
29	Correct	2170 ms	114464 KB	Output is correct
30	Correct	2315 ms	117748 KB	Output is correct
31	Correct	2326 ms	117904 KB	Output is correct
32	Correct	2275 ms	117584 KB	Output is correct
33	Correct	2332 ms	117588 KB	Output is correct
34	Correct	2333 ms	117588 KB	Output is correct
35	Correct	2343 ms	117580 KB	Output is correct
36	Correct	2471 ms	117744 KB	Output is correct
37	Correct	2463 ms	117748 KB	Output is correct
38	Correct	2373 ms	117524 KB	Output is correct
39	Correct	2354 ms	117588 KB	Output is correct
40	Correct	2339 ms	117592 KB	Output is correct
41	Correct	2370 ms	117584 KB	Output is correct
42	Correct	2353 ms	117584 KB	Output is correct

Subtask #4
0 / 26.0

#	결과	실행 시간	메모리	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	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	464 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	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	2 ms	1372 KB	Output is correct
18	Correct	8 ms	3528 KB	Output is correct
19	Correct	8 ms	3532 KB	Output is correct
20	Correct	8 ms	3420 KB	Output is correct
21	Correct	7 ms	3420 KB	Output is correct
22	Correct	7 ms	3420 KB	Output is correct
23	Correct	11 ms	3416 KB	Output is correct
24	Correct	7 ms	3420 KB	Output is correct
25	Correct	7 ms	3420 KB	Output is correct
26	Correct	7 ms	3420 KB	Output is correct
27	Correct	7 ms	3420 KB	Output is correct
28	Correct	7 ms	3420 KB	Output is correct
29	Correct	2170 ms	114464 KB	Output is correct
30	Correct	2315 ms	117748 KB	Output is correct
31	Correct	2326 ms	117904 KB	Output is correct
32	Correct	2275 ms	117584 KB	Output is correct
33	Correct	2332 ms	117588 KB	Output is correct
34	Correct	2333 ms	117588 KB	Output is correct
35	Correct	2343 ms	117580 KB	Output is correct
36	Correct	2471 ms	117744 KB	Output is correct
37	Correct	2463 ms	117748 KB	Output is correct
38	Correct	2373 ms	117524 KB	Output is correct
39	Correct	2354 ms	117588 KB	Output is correct
40	Correct	2339 ms	117592 KB	Output is correct
41	Correct	2370 ms	117584 KB	Output is correct
42	Correct	2353 ms	117584 KB	Output is correct
43	Runtime error	4 ms	1576 KB	Execution killed with signal 11
44	Halted	0 ms	0 KB	-

Subtask #5
0 / 13.0

#	결과	실행 시간	메모리	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	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	464 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	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	2 ms	1372 KB	Output is correct
18	Correct	8 ms	3528 KB	Output is correct
19	Correct	8 ms	3532 KB	Output is correct
20	Correct	8 ms	3420 KB	Output is correct
21	Correct	7 ms	3420 KB	Output is correct
22	Correct	7 ms	3420 KB	Output is correct
23	Correct	11 ms	3416 KB	Output is correct
24	Correct	7 ms	3420 KB	Output is correct
25	Correct	7 ms	3420 KB	Output is correct
26	Correct	7 ms	3420 KB	Output is correct
27	Correct	7 ms	3420 KB	Output is correct
28	Correct	7 ms	3420 KB	Output is correct
29	Correct	2170 ms	114464 KB	Output is correct
30	Correct	2315 ms	117748 KB	Output is correct
31	Correct	2326 ms	117904 KB	Output is correct
32	Correct	2275 ms	117584 KB	Output is correct
33	Correct	2332 ms	117588 KB	Output is correct
34	Correct	2333 ms	117588 KB	Output is correct
35	Correct	2343 ms	117580 KB	Output is correct
36	Correct	2471 ms	117744 KB	Output is correct
37	Correct	2463 ms	117748 KB	Output is correct
38	Correct	2373 ms	117524 KB	Output is correct
39	Correct	2354 ms	117588 KB	Output is correct
40	Correct	2339 ms	117592 KB	Output is correct
41	Correct	2370 ms	117584 KB	Output is correct
42	Correct	2353 ms	117584 KB	Output is correct
43	Runtime error	4 ms	1576 KB	Execution killed with signal 11
44	Halted	0 ms	0 KB	-

답안 #1094838

Compilation message

Subtask #1 16.0 / 16.0

Subtask #2 24.0 / 24.0

Subtask #3 21.0 / 21.0

Subtask #4 0 / 26.0

Subtask #5 0 / 13.0

Subtask #1
16.0 / 16.0

Subtask #2
24.0 / 24.0

Subtask #3
21.0 / 21.0

Subtask #4
0 / 26.0

Subtask #5
0 / 13.0