oj.uz

Submission #938140

# Submission time Handle Problem Language Result Execution time Memory
938140 2024-03-04T22:19:30 Z Ice_man Chorus (JOI23_chorus) C++14
40 / 100
 6414 ms 32348 KB 
#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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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 -