답안 #889706

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
889706	2023-12-20T05:52:06 Z	vjudge1	Chorus (JOI23_chorus)	C++17	16 / 100	7000 ms	456 KB

chorus

#include <bits/stdc++.h>

using namespace std;

#define all(x) x.begin(), x.end()
#define ar array
#define pb push_back
#define ln '\n'
#define int long long

using i64 = long long;

template <class F, class _S>
bool chmin(F &u, const _S &v){
    bool flag = false;
    if ( u > v ){
        u = v; flag |= true;
    }
    return flag;
}

template <class F, class _S>
bool chmax(F &u, const _S &v){
    bool flag = false;
    if ( u < v ){
        u = v; flag |= true;
    }
    return flag;
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, k; cin >> n >> k;
    string s; cin >> s;
    int m = s.size();
    auto get = [&](auto &u){ return u == 'A' ? -1 : 1; };
    auto ok = [&](auto &s){
        queue <int> q;
        vector <int> nxt(m, m + 1);
        for ( int i = m - 1; i >= 0; i-- ){
            if ( s[i] == 'B' ) q.push(i);
            else{
                if ( q.empty() ){
                    return false;
                }
                nxt[i] = q.front();
                q.pop();
            }
        }
        int cnt = 1, lst = -1;
        vector <int> c(m);
        for ( int i = m - 1; i >= 0; i-- ){
            if ( s[i] != 'B' ) continue;
            if ( lst == -1 ){
                lst = i;
                c[lst] = i;
            } else{
                int mn = m + 1;
                for ( int k = lst - 1; k > i; k-- ){
                    chmin(mn, nxt[k]);
                }
                if ( mn <= c[lst] ){
                    c[i] = i;
                    ++cnt;
                } else c[i] = c[lst];
                lst = i;
            }
        }
        return cnt <= k;
    };
    vector <int> a;
    for ( int i = 0; i < m; i++ ){
        if ( s[i] == 'B' ) a.pb(i);
    }
    auto t = s;
    sort(all(t));
    int mn = n * n + 1;
    do{
        if ( !ok(t) ) continue;
        vector <int> b;
        for ( int i = 0; i < m; i++ ){
            if ( t[i] == 'B' ) b.pb(i);
        }
        int ans = 0;
        for ( int i = 0; i < n; i++ ){
            ans += abs(a[i] - b[i]);
        }
        auto flag = chmin(mn, ans);
    } while ( next_permutation(all(t)) );
    cout << mn;

    cout << '\n';
}

Compilation message

chorus.cpp: In function 'int main()':
chorus.cpp:90:14: warning: unused variable 'flag' [-Wunused-variable]
   90 |         auto flag = chmin(mn, ans);
      |              ^~~~
chorus.cpp:38:10: warning: variable 'get' set but not used [-Wunused-but-set-variable]
   38 |     auto get = [&](auto &u){ return u == 'A' ? -1 : 1; };
      |          ^~~

Subtask #1

16.0 / 16.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	16 ms	456 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	1 ms	344 KB	Output is correct
7	Correct	15 ms	348 KB	Output is correct
8	Correct	15 ms	344 KB	Output is correct
9	Correct	15 ms	348 KB	Output is correct
10	Correct	15 ms	452 KB	Output is correct
11	Correct	18 ms	452 KB	Output is correct
12	Correct	18 ms	344 KB	Output is correct
13	Correct	18 ms	348 KB	Output is correct
14	Correct	15 ms	348 KB	Output is correct
15	Correct	16 ms	348 KB	Output is correct
16	Correct	17 ms	348 KB	Output is correct

Subtask #2

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	16 ms	456 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	1 ms	344 KB	Output is correct
7	Correct	15 ms	348 KB	Output is correct
8	Correct	15 ms	344 KB	Output is correct
9	Correct	15 ms	348 KB	Output is correct
10	Correct	15 ms	452 KB	Output is correct
11	Correct	18 ms	452 KB	Output is correct
12	Correct	18 ms	344 KB	Output is correct
13	Correct	18 ms	348 KB	Output is correct
14	Correct	15 ms	348 KB	Output is correct
15	Correct	16 ms	348 KB	Output is correct
16	Correct	17 ms	348 KB	Output is correct
17	Execution timed out	7027 ms	348 KB	Time limit exceeded
18	Halted	0 ms	0 KB	-

Subtask #3

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	16 ms	456 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	1 ms	344 KB	Output is correct
7	Correct	15 ms	348 KB	Output is correct
8	Correct	15 ms	344 KB	Output is correct
9	Correct	15 ms	348 KB	Output is correct
10	Correct	15 ms	452 KB	Output is correct
11	Correct	18 ms	452 KB	Output is correct
12	Correct	18 ms	344 KB	Output is correct
13	Correct	18 ms	348 KB	Output is correct
14	Correct	15 ms	348 KB	Output is correct
15	Correct	16 ms	348 KB	Output is correct
16	Correct	17 ms	348 KB	Output is correct
17	Execution timed out	7027 ms	348 KB	Time limit exceeded
18	Halted	0 ms	0 KB	-

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	16 ms	456 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	1 ms	344 KB	Output is correct
7	Correct	15 ms	348 KB	Output is correct
8	Correct	15 ms	344 KB	Output is correct
9	Correct	15 ms	348 KB	Output is correct
10	Correct	15 ms	452 KB	Output is correct
11	Correct	18 ms	452 KB	Output is correct
12	Correct	18 ms	344 KB	Output is correct
13	Correct	18 ms	348 KB	Output is correct
14	Correct	15 ms	348 KB	Output is correct
15	Correct	16 ms	348 KB	Output is correct
16	Correct	17 ms	348 KB	Output is correct
17	Execution timed out	7027 ms	348 KB	Time limit exceeded
18	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	16 ms	456 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	1 ms	344 KB	Output is correct
7	Correct	15 ms	348 KB	Output is correct
8	Correct	15 ms	344 KB	Output is correct
9	Correct	15 ms	348 KB	Output is correct
10	Correct	15 ms	452 KB	Output is correct
11	Correct	18 ms	452 KB	Output is correct
12	Correct	18 ms	344 KB	Output is correct
13	Correct	18 ms	348 KB	Output is correct
14	Correct	15 ms	348 KB	Output is correct
15	Correct	16 ms	348 KB	Output is correct
16	Correct	17 ms	348 KB	Output is correct
17	Execution timed out	7027 ms	348 KB	Time limit exceeded
18	Halted	0 ms	0 KB	-