Submission #1090377

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1090377	2024-09-18T09:52:13 Z	eltu0815	Chorus (JOI23_chorus)	C++14	16 / 100	7000 ms	4440 KB

chorus

#include <bits/stdc++.h>
#define MAX 300005
#define MOD (ll)(1048573)
#define INF (ll)(1e18)
#define inf (int)(1e9)
#define eps (double)(1e-8)
 
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
int tt, n, m, k, q;
string str;

int cnt[MAX];
ll dp[5005][5005];

ll cost(int i, int j) {
    ll ret = 0;
    for(int k = i; k <= j; ++k) {
        ret += max(0, - (i - 1) + cnt[k]);
    }
    return ret;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(NULL);
    
    cin >> n >> k >> str;
    for(int i = 0, tmp = 0, p = 0; i < 2 * n; ++i) {
        if(str[i] == 'A') cnt[++p] = tmp;
        else ++tmp;
    }
    
    for(int i = 0; i <= n; ++i) for(int j = 0; j <= k; ++j) dp[i][j] = INF;
    
    dp[0][0] = 0;
    for(int i = 1; i <= n; ++i) for(int j = 1; j <= k; ++j) {
        for(int ii = 0; ii < i; ++ii) {
            dp[i][j] = min(dp[i][j], dp[ii][j - 1] + cost(ii + 1, i));
        }
    }
    
    cout << dp[n][k];
    return 0;
}

Subtask #1

16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	0 ms	460 KB	Output is correct
3	Correct	0 ms	344 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	1 ms	460 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	1 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

Subtask #2

0 / 24.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	0 ms	460 KB	Output is correct
3	Correct	0 ms	344 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	1 ms	460 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	1 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	38 ms	1116 KB	Output is correct
18	Correct	1386 ms	2652 KB	Output is correct
19	Correct	3989 ms	3552 KB	Output is correct
20	Correct	16 ms	2516 KB	Output is correct
21	Correct	30 ms	2396 KB	Output is correct
22	Execution timed out	7003 ms	4440 KB	Time limit exceeded
23	Halted	0 ms	0 KB	-

Subtask #3

0 / 21.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	0 ms	460 KB	Output is correct
3	Correct	0 ms	344 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	1 ms	460 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	1 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	38 ms	1116 KB	Output is correct
18	Correct	1386 ms	2652 KB	Output is correct
19	Correct	3989 ms	3552 KB	Output is correct
20	Correct	16 ms	2516 KB	Output is correct
21	Correct	30 ms	2396 KB	Output is correct
22	Execution timed out	7003 ms	4440 KB	Time limit exceeded
23	Halted	0 ms	0 KB	-

Subtask #4

0 / 26.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	0 ms	460 KB	Output is correct
3	Correct	0 ms	344 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	1 ms	460 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	1 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	38 ms	1116 KB	Output is correct
18	Correct	1386 ms	2652 KB	Output is correct
19	Correct	3989 ms	3552 KB	Output is correct
20	Correct	16 ms	2516 KB	Output is correct
21	Correct	30 ms	2396 KB	Output is correct
22	Execution timed out	7003 ms	4440 KB	Time limit exceeded
23	Halted	0 ms	0 KB	-

Subtask #5

0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	0 ms	460 KB	Output is correct
3	Correct	0 ms	344 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	1 ms	460 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	1 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	38 ms	1116 KB	Output is correct
18	Correct	1386 ms	2652 KB	Output is correct
19	Correct	3989 ms	3552 KB	Output is correct
20	Correct	16 ms	2516 KB	Output is correct
21	Correct	30 ms	2396 KB	Output is correct
22	Execution timed out	7003 ms	4440 KB	Time limit exceeded
23	Halted	0 ms	0 KB	-