답안 #938140

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
938140	2024-03-04T22:19:30 Z	Ice_man	Chorus (JOI23_chorus)	C++14	40 / 100	6414 ms	32348 KB

chorus

#include <iostream>
#include <chrono>

#define maxn 2005
#define maxlog 20
#define INF 1000000010
#define LINF 1000000000000000005
#define endl '\n'
#define pb(x) push_back(x)
#define X first
#define Y second
#define control cout<<"passed"<<endl;

#pragma GCC optimize("O3" , "Ofast" , "unroll-loops" , "fast-math")
#pragma GCC target("avx2")

using namespace std;

std::chrono::high_resolution_clock::time_point startT, currT;
constexpr double TIME_MULT = 1;

double timePassed()
{
    using namespace std::chrono;
    currT = high_resolution_clock::now();
    double time = duration_cast<duration<double>>(currT - startT).count();
    return time * TIME_MULT;
}


int n , k;
string s;

void read()
{
    cin >> n >> k;
    cin >> s;
}

int dp[maxn][maxn] , a[maxn];
int bra , brb;

int calc(int y , int x)
{
    int ret = 0;

    for(int i = y + 1; i <= x; i++)
        if(a[i] >= y)
            ret += a[i] - y;

    return ret;
}


void calc_dp()
{
    bra = 0;
    brb = 0;

    for(char c : s)
        if(c == 'A')
        {
            bra++;
            a[bra] = brb;
        }
        else
            brb++;

    /**for(int i = 0; i < 2 * n; i++)
        cout << a[i] << " ";
    cout << endl;

    cout << bra << " " << brb << endl;*/

    for(int i = 0; i <= k; i++)
        for(int j = 0; j <= n; j++)
            dp[i][j] = INF;

    dp[0][0] = 0;

    for(int i = 1; i <= k; i++)
        for(int j = 1; j <= n; j++)
            for(int _k = 0; _k < j; _k++)
            {
                ///cout << calc(_k , j) << endl;
                dp[i][j] = min(dp[i][j] , dp[i - 1][_k] + calc(_k , j));
            }


    cout << dp[k][n] << endl;
}




int main()
{

    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    startT = std::chrono::high_resolution_clock::now();

    read();
    calc_dp();


    return 0;
}

Subtask #1
16.0 / 16.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	1 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	1 ms	344 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	452 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	0 ms	464 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	0 ms	464 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	0 ms	348 KB	Output is correct
16	Correct	1 ms	348 KB	Output is correct

Subtask #2
24.0 / 24.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	1 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	1 ms	344 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	452 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	0 ms	464 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	0 ms	464 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	0 ms	348 KB	Output is correct
16	Correct	1 ms	348 KB	Output is correct
17	Correct	33 ms	2512 KB	Output is correct
18	Correct	1202 ms	2628 KB	Output is correct
19	Correct	3515 ms	2652 KB	Output is correct
20	Correct	14 ms	348 KB	Output is correct
21	Correct	27 ms	460 KB	Output is correct
22	Correct	6403 ms	4676 KB	Output is correct
23	Correct	6414 ms	4700 KB	Output is correct
24	Correct	132 ms	508 KB	Output is correct
25	Correct	6410 ms	4676 KB	Output is correct
26	Correct	5502 ms	4680 KB	Output is correct
27	Correct	2231 ms	2628 KB	Output is correct
28	Correct	2255 ms	2652 KB	Output is correct

Subtask #3
0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	1 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	1 ms	344 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	452 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	0 ms	464 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	0 ms	464 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	0 ms	348 KB	Output is correct
16	Correct	1 ms	348 KB	Output is correct
17	Correct	33 ms	2512 KB	Output is correct
18	Correct	1202 ms	2628 KB	Output is correct
19	Correct	3515 ms	2652 KB	Output is correct
20	Correct	14 ms	348 KB	Output is correct
21	Correct	27 ms	460 KB	Output is correct
22	Correct	6403 ms	4676 KB	Output is correct
23	Correct	6414 ms	4700 KB	Output is correct
24	Correct	132 ms	508 KB	Output is correct
25	Correct	6410 ms	4676 KB	Output is correct
26	Correct	5502 ms	4680 KB	Output is correct
27	Correct	2231 ms	2628 KB	Output is correct
28	Correct	2255 ms	2652 KB	Output is correct
29	Runtime error	20 ms	32348 KB	Execution killed with signal 11
30	Halted	0 ms	0 KB	-

Subtask #4
0 / 26.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	1 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	1 ms	344 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	452 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	0 ms	464 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	0 ms	464 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	0 ms	348 KB	Output is correct
16	Correct	1 ms	348 KB	Output is correct
17	Correct	33 ms	2512 KB	Output is correct
18	Correct	1202 ms	2628 KB	Output is correct
19	Correct	3515 ms	2652 KB	Output is correct
20	Correct	14 ms	348 KB	Output is correct
21	Correct	27 ms	460 KB	Output is correct
22	Correct	6403 ms	4676 KB	Output is correct
23	Correct	6414 ms	4700 KB	Output is correct
24	Correct	132 ms	508 KB	Output is correct
25	Correct	6410 ms	4676 KB	Output is correct
26	Correct	5502 ms	4680 KB	Output is correct
27	Correct	2231 ms	2628 KB	Output is correct
28	Correct	2255 ms	2652 KB	Output is correct
29	Runtime error	20 ms	32348 KB	Execution killed with signal 11
30	Halted	0 ms	0 KB	-

Subtask #5
0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	1 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	1 ms	344 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	452 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	0 ms	464 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	0 ms	464 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	0 ms	348 KB	Output is correct
16	Correct	1 ms	348 KB	Output is correct
17	Correct	33 ms	2512 KB	Output is correct
18	Correct	1202 ms	2628 KB	Output is correct
19	Correct	3515 ms	2652 KB	Output is correct
20	Correct	14 ms	348 KB	Output is correct
21	Correct	27 ms	460 KB	Output is correct
22	Correct	6403 ms	4676 KB	Output is correct
23	Correct	6414 ms	4700 KB	Output is correct
24	Correct	132 ms	508 KB	Output is correct
25	Correct	6410 ms	4676 KB	Output is correct
26	Correct	5502 ms	4680 KB	Output is correct
27	Correct	2231 ms	2628 KB	Output is correct
28	Correct	2255 ms	2652 KB	Output is correct
29	Runtime error	20 ms	32348 KB	Execution killed with signal 11
30	Halted	0 ms	0 KB	-

답안 #938140

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