Submission #901562

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
901562	2024-01-09T14:57:13 Z	Tuanlinh123	Chorus (JOI23_chorus)	C++17	16 / 100	7000 ms	4700 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 n, k, a[maxn], dp[maxn][maxn];

ll cost(ll j, ll i)
{
    ll ans=0;
    for (ll k=j+1; k<=i; k++)
        if (a[k]>=j)
            ans+=a[k]-j;
    return ans;
}

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++, a[x]=y;
        else y++;
    }
    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];
}

Compilation message

chorus.cpp: In function 'int main()':
chorus.cpp:29:18: warning: unused variable 'crr' [-Wunused-variable]
   29 |     ll x=0, y=0, crr=1;
      |                  ^~~

Subtask #1

16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 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	348 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	344 KB	Output is correct
12	Correct	0 ms	344 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	0 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	348 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	344 KB	Output is correct
12	Correct	0 ms	344 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	43 ms	2612 KB	Output is correct
18	Correct	1489 ms	2692 KB	Output is correct
19	Correct	4273 ms	2676 KB	Output is correct
20	Correct	16 ms	348 KB	Output is correct
21	Correct	31 ms	348 KB	Output is correct
22	Execution timed out	7092 ms	4700 KB	Time limit exceeded
23	Halted	0 ms	0 KB	-

Subtask #3

0 / 21.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 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	348 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	344 KB	Output is correct
12	Correct	0 ms	344 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	43 ms	2612 KB	Output is correct
18	Correct	1489 ms	2692 KB	Output is correct
19	Correct	4273 ms	2676 KB	Output is correct
20	Correct	16 ms	348 KB	Output is correct
21	Correct	31 ms	348 KB	Output is correct
22	Execution timed out	7092 ms	4700 KB	Time limit exceeded
23	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	0 ms	348 KB	Output is correct
3	Correct	0 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	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	344 KB	Output is correct
12	Correct	0 ms	344 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	43 ms	2612 KB	Output is correct
18	Correct	1489 ms	2692 KB	Output is correct
19	Correct	4273 ms	2676 KB	Output is correct
20	Correct	16 ms	348 KB	Output is correct
21	Correct	31 ms	348 KB	Output is correct
22	Execution timed out	7092 ms	4700 KB	Time limit exceeded
23	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	0 ms	348 KB	Output is correct
3	Correct	0 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	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	344 KB	Output is correct
12	Correct	0 ms	344 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	43 ms	2612 KB	Output is correct
18	Correct	1489 ms	2692 KB	Output is correct
19	Correct	4273 ms	2676 KB	Output is correct
20	Correct	16 ms	348 KB	Output is correct
21	Correct	31 ms	348 KB	Output is correct
22	Execution timed out	7092 ms	4700 KB	Time limit exceeded
23	Halted	0 ms	0 KB	-