Submission #825344

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
825344	2023-08-14T18:19:42 Z	grogu	Chorus (JOI23_chorus)	C++14	40 / 100	87 ms	4328 KB

chorus

#define here cerr<<"===========================================\n"
#define dbg(x) cerr<<#x<<": "<<x<<endl;
#include <bits/stdc++.h>
#define ld double
#define ll long long
#define ull unsigned long long
#define llinf 100000000000000000LL // 10^17
#define iinf 2000000000 // 2*10^9
#define pb push_back
#define eb emplace_back
#define popb pop_back
#define fi first
#define sc second
#define endl '\n'
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pld pair<ld,ld>
#define all(a) a.begin(),a.end()
#define ceri(a,l,r) {cerr<<#a<<": ";for(ll i_ = l;i_<=r;i_++) cerr<<a[i_]<< " ";cerr<<endl;}
#define cer(a) {cerr<<#a<<": ";for(ll x_ : a) cerr<<x_<< " ";cerr<<endl;}
#define si(a) (ll)(a.size())
using namespace std;


#define maxn 5005
ll n,k;
ll a[maxn];
ll c[maxn];
ll ps[maxn];
ll sz = 0;
ll dp[maxn][maxn];
int main(){
	ios_base::sync_with_stdio(false);cerr.tie(0);cout.tie(0);cin.tie(0);
    cin >> n >> k;
    string s; cin >> s;
    for(ll i = 1;i<=2*n;i++){
        if(s[i-1]=='A') a[i] = 1;
    }
    ll b = 0;
    for(ll i = 2*n;i>=1;i--){
        if(a[i]==1){
            c[++sz] = b;
        }else b++;
    }
    for(ll i = 1;i<=n;i++) ps[i] = ps[i-1] + c[i];
    dp[0][0] = 0;
    for(ll i = 1;i<=n;i++) dp[i][0] = llinf;
    for(ll j = 1;j<=k;j++){
        for(ll i = 1;i<=n;i++){
            dp[i][j] = llinf;
            ll sum = 0;
            for(ll e = i;e>=1;e--){
                sum+=max(0LL,i-c[e]);
                dp[i][j] = min(dp[i][j],dp[e-1][j-1]+sum);
            }
        }
    }
    cout<<dp[n][k]<<endl;
	return (0-0);
}
/**
5 2
AABABABBAB

**/

Subtask #1
16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	340 KB	Output is correct
2	Correct	0 ms	328 KB	Output is correct
3	Correct	0 ms	340 KB	Output is correct
4	Correct	0 ms	340 KB	Output is correct
5	Correct	0 ms	328 KB	Output is correct
6	Correct	0 ms	340 KB	Output is correct
7	Correct	0 ms	340 KB	Output is correct
8	Correct	1 ms	340 KB	Output is correct
9	Correct	0 ms	328 KB	Output is correct
10	Correct	0 ms	324 KB	Output is correct
11	Correct	0 ms	340 KB	Output is correct
12	Correct	0 ms	340 KB	Output is correct
13	Correct	1 ms	340 KB	Output is correct
14	Correct	0 ms	340 KB	Output is correct
15	Correct	0 ms	340 KB	Output is correct
16	Correct	0 ms	324 KB	Output is correct

Subtask #2
24.0 / 24.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	340 KB	Output is correct
2	Correct	0 ms	328 KB	Output is correct
3	Correct	0 ms	340 KB	Output is correct
4	Correct	0 ms	340 KB	Output is correct
5	Correct	0 ms	328 KB	Output is correct
6	Correct	0 ms	340 KB	Output is correct
7	Correct	0 ms	340 KB	Output is correct
8	Correct	1 ms	340 KB	Output is correct
9	Correct	0 ms	328 KB	Output is correct
10	Correct	0 ms	324 KB	Output is correct
11	Correct	0 ms	340 KB	Output is correct
12	Correct	0 ms	340 KB	Output is correct
13	Correct	1 ms	340 KB	Output is correct
14	Correct	0 ms	340 KB	Output is correct
15	Correct	0 ms	340 KB	Output is correct
16	Correct	0 ms	324 KB	Output is correct
17	Correct	2 ms	1108 KB	Output is correct
18	Correct	15 ms	2636 KB	Output is correct
19	Correct	40 ms	3412 KB	Output is correct
20	Correct	1 ms	2388 KB	Output is correct
21	Correct	1 ms	2388 KB	Output is correct
22	Correct	87 ms	4328 KB	Output is correct
23	Correct	72 ms	4292 KB	Output is correct
24	Correct	3 ms	2388 KB	Output is correct
25	Correct	74 ms	4220 KB	Output is correct
26	Correct	66 ms	3892 KB	Output is correct
27	Correct	25 ms	2956 KB	Output is correct
28	Correct	25 ms	3020 KB	Output is correct

Subtask #3
0 / 21.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	340 KB	Output is correct
2	Correct	0 ms	328 KB	Output is correct
3	Correct	0 ms	340 KB	Output is correct
4	Correct	0 ms	340 KB	Output is correct
5	Correct	0 ms	328 KB	Output is correct
6	Correct	0 ms	340 KB	Output is correct
7	Correct	0 ms	340 KB	Output is correct
8	Correct	1 ms	340 KB	Output is correct
9	Correct	0 ms	328 KB	Output is correct
10	Correct	0 ms	324 KB	Output is correct
11	Correct	0 ms	340 KB	Output is correct
12	Correct	0 ms	340 KB	Output is correct
13	Correct	1 ms	340 KB	Output is correct
14	Correct	0 ms	340 KB	Output is correct
15	Correct	0 ms	340 KB	Output is correct
16	Correct	0 ms	324 KB	Output is correct
17	Correct	2 ms	1108 KB	Output is correct
18	Correct	15 ms	2636 KB	Output is correct
19	Correct	40 ms	3412 KB	Output is correct
20	Correct	1 ms	2388 KB	Output is correct
21	Correct	1 ms	2388 KB	Output is correct
22	Correct	87 ms	4328 KB	Output is correct
23	Correct	72 ms	4292 KB	Output is correct
24	Correct	3 ms	2388 KB	Output is correct
25	Correct	74 ms	4220 KB	Output is correct
26	Correct	66 ms	3892 KB	Output is correct
27	Correct	25 ms	2956 KB	Output is correct
28	Correct	25 ms	3020 KB	Output is correct
29	Runtime error	4 ms	624 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	340 KB	Output is correct
2	Correct	0 ms	328 KB	Output is correct
3	Correct	0 ms	340 KB	Output is correct
4	Correct	0 ms	340 KB	Output is correct
5	Correct	0 ms	328 KB	Output is correct
6	Correct	0 ms	340 KB	Output is correct
7	Correct	0 ms	340 KB	Output is correct
8	Correct	1 ms	340 KB	Output is correct
9	Correct	0 ms	328 KB	Output is correct
10	Correct	0 ms	324 KB	Output is correct
11	Correct	0 ms	340 KB	Output is correct
12	Correct	0 ms	340 KB	Output is correct
13	Correct	1 ms	340 KB	Output is correct
14	Correct	0 ms	340 KB	Output is correct
15	Correct	0 ms	340 KB	Output is correct
16	Correct	0 ms	324 KB	Output is correct
17	Correct	2 ms	1108 KB	Output is correct
18	Correct	15 ms	2636 KB	Output is correct
19	Correct	40 ms	3412 KB	Output is correct
20	Correct	1 ms	2388 KB	Output is correct
21	Correct	1 ms	2388 KB	Output is correct
22	Correct	87 ms	4328 KB	Output is correct
23	Correct	72 ms	4292 KB	Output is correct
24	Correct	3 ms	2388 KB	Output is correct
25	Correct	74 ms	4220 KB	Output is correct
26	Correct	66 ms	3892 KB	Output is correct
27	Correct	25 ms	2956 KB	Output is correct
28	Correct	25 ms	3020 KB	Output is correct
29	Runtime error	4 ms	624 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	340 KB	Output is correct
2	Correct	0 ms	328 KB	Output is correct
3	Correct	0 ms	340 KB	Output is correct
4	Correct	0 ms	340 KB	Output is correct
5	Correct	0 ms	328 KB	Output is correct
6	Correct	0 ms	340 KB	Output is correct
7	Correct	0 ms	340 KB	Output is correct
8	Correct	1 ms	340 KB	Output is correct
9	Correct	0 ms	328 KB	Output is correct
10	Correct	0 ms	324 KB	Output is correct
11	Correct	0 ms	340 KB	Output is correct
12	Correct	0 ms	340 KB	Output is correct
13	Correct	1 ms	340 KB	Output is correct
14	Correct	0 ms	340 KB	Output is correct
15	Correct	0 ms	340 KB	Output is correct
16	Correct	0 ms	324 KB	Output is correct
17	Correct	2 ms	1108 KB	Output is correct
18	Correct	15 ms	2636 KB	Output is correct
19	Correct	40 ms	3412 KB	Output is correct
20	Correct	1 ms	2388 KB	Output is correct
21	Correct	1 ms	2388 KB	Output is correct
22	Correct	87 ms	4328 KB	Output is correct
23	Correct	72 ms	4292 KB	Output is correct
24	Correct	3 ms	2388 KB	Output is correct
25	Correct	74 ms	4220 KB	Output is correct
26	Correct	66 ms	3892 KB	Output is correct
27	Correct	25 ms	2956 KB	Output is correct
28	Correct	25 ms	3020 KB	Output is correct
29	Runtime error	4 ms	624 KB	Execution killed with signal 11
30	Halted	0 ms	0 KB	-

Submission #825344

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