답안 #903400

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
903400	2024-01-11T07:31:31 Z	CDuong	Chorus (JOI23_chorus)	C++17	40 / 100	72 ms	2396 KB

chorus

/*
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,fma,bmi,bmi2,sse4.2,popcnt,lzcnt")
*/

#include <bits/stdc++.h>
#define taskname ""
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define i64 long long
#define i128 __int128
#define pb push_back
#define ff first
#define ss second
#define isz(x) (int)x.size()
using namespace std;

const int mxN = 2e5 + 5;
const int mod = 1e9 + 7;
const i64 oo = 1e18;

int n, k;
int pfx[505], dp[505][505], min_swap[505][505];
string s;
vector<int> posA, posB;

int sum_range(int l, int r) {
    if (l > r) return 0;
    return (l + r) * (r - l + 1) / 2;
}

int calcA(int l, int r) {
    if (l > r) return 0;
    return (l == 0 ? pfx[r] : pfx[r] - pfx[l - 1]);
}

void upd(int &val, int nval) {
    val = (val == -1 ? nval : (val < nval ? val : nval));
}

void solve() {
    cin >> n >> k >> s; s = " " + s;
    if (n > 500) return;
    for (int i = 1; i <= 2 * n; ++i) {
        if (s[i] == 'A') posA.emplace_back(i);
        else posB.emplace_back(i);
    }
    partial_sum(all(posA), pfx);
    for (int l = 0; l < n; ++l) {
        for (int r = l; r < n; ++r) {
            int pos = lower_bound(posA.begin() + l, posA.begin() + r + 1, posB[l]) - posA.begin();
            int offset = 0;
            if (pos <= r) offset = count(s.begin() + posB[l], s.begin() + posA[pos], 'A');
            min_swap[l + 1][r + 1] = calcA(pos, r) - sum_range(posB[l] + offset, posB[l] + offset + (r - pos + 1) - 1);
            // cout << l + 1 << " " << r + 1 << " " << min_swap[l + 1][r + 1] << endl;
        }
        // cout << "\n";
    }
    memset(dp, -1, sizeof dp);
    dp[0][0] = 0;
    for (int j = 0; j < k; ++j) {
        for (int i = 0; i < n; ++i) if (dp[i][j] != -1) {
            for (int ni = i + 1; ni <= n; ++ni) {
                upd(dp[ni][j + 1], dp[i][j] + min_swap[i + 1][ni]);
            }
        }
    }
    cout << dp[n][k] << endl;
}

signed main() {

#ifndef CDuongg
    if(fopen(taskname".inp", "r"))
        assert(freopen(taskname".inp", "r", stdin)), assert(freopen(taskname".out", "w", stdout));
#else
    freopen("bai3.inp", "r", stdin);
    freopen("bai3.out", "w", stdout);
    auto start = chrono::high_resolution_clock::now();
#endif

    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1; //cin >> t;
    while(t--) solve();

#ifdef CDuongg
   auto end = chrono::high_resolution_clock::now();
   cout << "\n"; for(int i = 1; i <= 100; ++i) cout << '=';
   cout << "\nExecution time: " << chrono::duration_cast<chrono::milliseconds> (end - start).count() << "[ms]" << endl;
   cout << "Check array size pls sir" << endl;
#endif

}

Subtask #1
16.0 / 16.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	1368 KB	Output is correct
2	Correct	1 ms	1372 KB	Output is correct
3	Correct	1 ms	1372 KB	Output is correct
4	Correct	1 ms	1372 KB	Output is correct
5	Correct	1 ms	1624 KB	Output is correct
6	Correct	1 ms	1372 KB	Output is correct
7	Correct	1 ms	1372 KB	Output is correct
8	Correct	1 ms	1368 KB	Output is correct
9	Correct	1 ms	1372 KB	Output is correct
10	Correct	1 ms	1372 KB	Output is correct
11	Correct	1 ms	1368 KB	Output is correct
12	Correct	1 ms	1372 KB	Output is correct
13	Correct	1 ms	1372 KB	Output is correct
14	Correct	1 ms	1236 KB	Output is correct
15	Correct	1 ms	1368 KB	Output is correct
16	Correct	1 ms	1372 KB	Output is correct

Subtask #2
24.0 / 24.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	1368 KB	Output is correct
2	Correct	1 ms	1372 KB	Output is correct
3	Correct	1 ms	1372 KB	Output is correct
4	Correct	1 ms	1372 KB	Output is correct
5	Correct	1 ms	1624 KB	Output is correct
6	Correct	1 ms	1372 KB	Output is correct
7	Correct	1 ms	1372 KB	Output is correct
8	Correct	1 ms	1368 KB	Output is correct
9	Correct	1 ms	1372 KB	Output is correct
10	Correct	1 ms	1372 KB	Output is correct
11	Correct	1 ms	1368 KB	Output is correct
12	Correct	1 ms	1372 KB	Output is correct
13	Correct	1 ms	1372 KB	Output is correct
14	Correct	1 ms	1236 KB	Output is correct
15	Correct	1 ms	1368 KB	Output is correct
16	Correct	1 ms	1372 KB	Output is correct
17	Correct	2 ms	1628 KB	Output is correct
18	Correct	11 ms	2396 KB	Output is correct
19	Correct	22 ms	2392 KB	Output is correct
20	Correct	40 ms	2388 KB	Output is correct
21	Correct	41 ms	2288 KB	Output is correct
22	Correct	64 ms	2384 KB	Output is correct
23	Correct	72 ms	2292 KB	Output is correct
24	Correct	4 ms	2392 KB	Output is correct
25	Correct	24 ms	2396 KB	Output is correct
26	Correct	25 ms	2392 KB	Output is correct
27	Correct	20 ms	2392 KB	Output is correct
28	Correct	17 ms	2396 KB	Output is correct

Subtask #3
0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	1368 KB	Output is correct
2	Correct	1 ms	1372 KB	Output is correct
3	Correct	1 ms	1372 KB	Output is correct
4	Correct	1 ms	1372 KB	Output is correct
5	Correct	1 ms	1624 KB	Output is correct
6	Correct	1 ms	1372 KB	Output is correct
7	Correct	1 ms	1372 KB	Output is correct
8	Correct	1 ms	1368 KB	Output is correct
9	Correct	1 ms	1372 KB	Output is correct
10	Correct	1 ms	1372 KB	Output is correct
11	Correct	1 ms	1368 KB	Output is correct
12	Correct	1 ms	1372 KB	Output is correct
13	Correct	1 ms	1372 KB	Output is correct
14	Correct	1 ms	1236 KB	Output is correct
15	Correct	1 ms	1368 KB	Output is correct
16	Correct	1 ms	1372 KB	Output is correct
17	Correct	2 ms	1628 KB	Output is correct
18	Correct	11 ms	2396 KB	Output is correct
19	Correct	22 ms	2392 KB	Output is correct
20	Correct	40 ms	2388 KB	Output is correct
21	Correct	41 ms	2288 KB	Output is correct
22	Correct	64 ms	2384 KB	Output is correct
23	Correct	72 ms	2292 KB	Output is correct
24	Correct	4 ms	2392 KB	Output is correct
25	Correct	24 ms	2396 KB	Output is correct
26	Correct	25 ms	2392 KB	Output is correct
27	Correct	20 ms	2392 KB	Output is correct
28	Correct	17 ms	2396 KB	Output is correct
29	Incorrect	1 ms	344 KB	Output isn't correct
30	Halted	0 ms	0 KB	-

Subtask #4
0 / 26.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	1368 KB	Output is correct
2	Correct	1 ms	1372 KB	Output is correct
3	Correct	1 ms	1372 KB	Output is correct
4	Correct	1 ms	1372 KB	Output is correct
5	Correct	1 ms	1624 KB	Output is correct
6	Correct	1 ms	1372 KB	Output is correct
7	Correct	1 ms	1372 KB	Output is correct
8	Correct	1 ms	1368 KB	Output is correct
9	Correct	1 ms	1372 KB	Output is correct
10	Correct	1 ms	1372 KB	Output is correct
11	Correct	1 ms	1368 KB	Output is correct
12	Correct	1 ms	1372 KB	Output is correct
13	Correct	1 ms	1372 KB	Output is correct
14	Correct	1 ms	1236 KB	Output is correct
15	Correct	1 ms	1368 KB	Output is correct
16	Correct	1 ms	1372 KB	Output is correct
17	Correct	2 ms	1628 KB	Output is correct
18	Correct	11 ms	2396 KB	Output is correct
19	Correct	22 ms	2392 KB	Output is correct
20	Correct	40 ms	2388 KB	Output is correct
21	Correct	41 ms	2288 KB	Output is correct
22	Correct	64 ms	2384 KB	Output is correct
23	Correct	72 ms	2292 KB	Output is correct
24	Correct	4 ms	2392 KB	Output is correct
25	Correct	24 ms	2396 KB	Output is correct
26	Correct	25 ms	2392 KB	Output is correct
27	Correct	20 ms	2392 KB	Output is correct
28	Correct	17 ms	2396 KB	Output is correct
29	Incorrect	1 ms	344 KB	Output isn't correct
30	Halted	0 ms	0 KB	-

Subtask #5
0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	1368 KB	Output is correct
2	Correct	1 ms	1372 KB	Output is correct
3	Correct	1 ms	1372 KB	Output is correct
4	Correct	1 ms	1372 KB	Output is correct
5	Correct	1 ms	1624 KB	Output is correct
6	Correct	1 ms	1372 KB	Output is correct
7	Correct	1 ms	1372 KB	Output is correct
8	Correct	1 ms	1368 KB	Output is correct
9	Correct	1 ms	1372 KB	Output is correct
10	Correct	1 ms	1372 KB	Output is correct
11	Correct	1 ms	1368 KB	Output is correct
12	Correct	1 ms	1372 KB	Output is correct
13	Correct	1 ms	1372 KB	Output is correct
14	Correct	1 ms	1236 KB	Output is correct
15	Correct	1 ms	1368 KB	Output is correct
16	Correct	1 ms	1372 KB	Output is correct
17	Correct	2 ms	1628 KB	Output is correct
18	Correct	11 ms	2396 KB	Output is correct
19	Correct	22 ms	2392 KB	Output is correct
20	Correct	40 ms	2388 KB	Output is correct
21	Correct	41 ms	2288 KB	Output is correct
22	Correct	64 ms	2384 KB	Output is correct
23	Correct	72 ms	2292 KB	Output is correct
24	Correct	4 ms	2392 KB	Output is correct
25	Correct	24 ms	2396 KB	Output is correct
26	Correct	25 ms	2392 KB	Output is correct
27	Correct	20 ms	2392 KB	Output is correct
28	Correct	17 ms	2396 KB	Output is correct
29	Incorrect	1 ms	344 KB	Output isn't correct
30	Halted	0 ms	0 KB	-

답안 #903400

Compilation message

Subtask #1 16.0 / 16.0

Subtask #2 24.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
24.0 / 24.0

Subtask #3
0 / 21.0

Subtask #4
0 / 26.0

Subtask #5
0 / 13.0