Submission #901563

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
901563	2024-01-09T14:58:24 Z	Tuanlinh123	Chorus (JOI23_chorus)	C++17	40 / 100	91 ms	4732 KB

chorus

#include<bits/stdc++.h>
#define ll long long
#define pll pair<ll, ll>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define ld long double
using namespace std;

const ll inf=2e9, maxn=1e3;
ll pre[maxn], to[maxn];
ll n, k, a[maxn], dp[maxn][maxn];

ll cost(ll j, ll i)
{
    if (to[j]>i) return 0;
    return (pre[i]-i*j)-(pre[to[j]-1]-(to[j]-1)*j);
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> n >> k;
    string s; cin >> s;
    ll x=0, y=0, crr=1;
    for (ll i=0; i<n*2; i++)
    {
        if (s[i]=='A')
            x++, pre[x]=pre[x-1]+y;
        else y++;
    }
    for (ll i=1; i<=n; i++)
        while (crr<=pre[i]-pre[i-1])
            to[crr]=i, crr++;
    while (crr<=n) to[crr]=n+1, crr++;
    for (ll i=1; i<=n; i++)
        if (to[i]<=i)
            to[i]=i+1;
    for (ll i=0; i<=k; i++)
        for (ll j=0; j<=n; j++)
            dp[i][j]=inf*inf;
    dp[0][0]=0;
    for (ll i=1; i<=k; i++)
        for (ll j=1; j<=n; j++)
            for (ll z=0; z<j; z++)
                dp[i][j]=min(dp[i][j], dp[i-1][z]+cost(z, j));
    cout << dp[k][n];
}

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	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	408 KB	Output is correct
5	Correct	0 ms	348 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	0 ms	348 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	0 ms	344 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	0 ms	372 KB	Output is correct
16	Correct	0 ms	348 KB	Output is correct

Subtask #2

24.0 / 24.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 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	0 ms	408 KB	Output is correct
5	Correct	0 ms	348 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	0 ms	348 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	0 ms	344 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	0 ms	372 KB	Output is correct
16	Correct	0 ms	348 KB	Output is correct
17	Correct	2 ms	2396 KB	Output is correct
18	Correct	17 ms	2700 KB	Output is correct
19	Correct	49 ms	2652 KB	Output is correct
20	Correct	1 ms	344 KB	Output is correct
21	Correct	1 ms	600 KB	Output is correct
22	Correct	89 ms	4700 KB	Output is correct
23	Correct	89 ms	4696 KB	Output is correct
24	Correct	2 ms	344 KB	Output is correct
25	Correct	90 ms	4700 KB	Output is correct
26	Correct	91 ms	4732 KB	Output is correct
27	Correct	33 ms	2680 KB	Output is correct
28	Correct	30 ms	2652 KB	Output is correct

Subtask #3

0 / 21.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 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	0 ms	408 KB	Output is correct
5	Correct	0 ms	348 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	0 ms	348 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	0 ms	344 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	0 ms	372 KB	Output is correct
16	Correct	0 ms	348 KB	Output is correct
17	Correct	2 ms	2396 KB	Output is correct
18	Correct	17 ms	2700 KB	Output is correct
19	Correct	49 ms	2652 KB	Output is correct
20	Correct	1 ms	344 KB	Output is correct
21	Correct	1 ms	600 KB	Output is correct
22	Correct	89 ms	4700 KB	Output is correct
23	Correct	89 ms	4696 KB	Output is correct
24	Correct	2 ms	344 KB	Output is correct
25	Correct	90 ms	4700 KB	Output is correct
26	Correct	91 ms	4732 KB	Output is correct
27	Correct	33 ms	2680 KB	Output is correct
28	Correct	30 ms	2652 KB	Output is correct
29	Runtime error	1 ms	604 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	1 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	0 ms	408 KB	Output is correct
5	Correct	0 ms	348 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	0 ms	348 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	0 ms	344 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	0 ms	372 KB	Output is correct
16	Correct	0 ms	348 KB	Output is correct
17	Correct	2 ms	2396 KB	Output is correct
18	Correct	17 ms	2700 KB	Output is correct
19	Correct	49 ms	2652 KB	Output is correct
20	Correct	1 ms	344 KB	Output is correct
21	Correct	1 ms	600 KB	Output is correct
22	Correct	89 ms	4700 KB	Output is correct
23	Correct	89 ms	4696 KB	Output is correct
24	Correct	2 ms	344 KB	Output is correct
25	Correct	90 ms	4700 KB	Output is correct
26	Correct	91 ms	4732 KB	Output is correct
27	Correct	33 ms	2680 KB	Output is correct
28	Correct	30 ms	2652 KB	Output is correct
29	Runtime error	1 ms	604 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	1 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	0 ms	408 KB	Output is correct
5	Correct	0 ms	348 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	0 ms	348 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	0 ms	344 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	0 ms	372 KB	Output is correct
16	Correct	0 ms	348 KB	Output is correct
17	Correct	2 ms	2396 KB	Output is correct
18	Correct	17 ms	2700 KB	Output is correct
19	Correct	49 ms	2652 KB	Output is correct
20	Correct	1 ms	344 KB	Output is correct
21	Correct	1 ms	600 KB	Output is correct
22	Correct	89 ms	4700 KB	Output is correct
23	Correct	89 ms	4696 KB	Output is correct
24	Correct	2 ms	344 KB	Output is correct
25	Correct	90 ms	4700 KB	Output is correct
26	Correct	91 ms	4732 KB	Output is correct
27	Correct	33 ms	2680 KB	Output is correct
28	Correct	30 ms	2652 KB	Output is correct
29	Runtime error	1 ms	604 KB	Execution killed with signal 11
30	Halted	0 ms	0 KB	-