Submission #834701

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
834701	2023-08-22T17:23:40 Z	Antekb	Chorus (JOI23_chorus)	C++17	40 / 100	7000 ms	79304 KB

chorus

#include<bits/stdc++.h>
#define st first
#define nd second
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define eb emplace_back
#define pp pop_back
#define mp make_pair
using namespace std;
using pii = pair<int, int>;
using ll = long long;
using vi = vector<int>;
using vii = vector<pii>;
void debug(){cerr<<"\n";}
template<typename H, typename... T>
void debug(H h, T... t){
	cerr<<h;
	if(sizeof...(t)){
		cerr<<", ";
	}
	debug(t...);
}
#define deb(x...) cerr<<#x<<" = ";debug(x);

mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

int main(){
	int n, k;
	string s;
	cin>>n>>k>>s;
	vi V(n+1);
	int a=0, b=1;
	for(char c:s){
		if(c=='A')a++;
		else{
			V[b]=a;
			b++;
		}
	}
	vector<vector<ll> > dp(n+1, vector<ll>(k+1, 1e18));
	dp[0][0]=0;
	for(int kk=1; kk<=k; kk++){
		for(int i=kk; i<=n; i++){
			for(int j=0; j<i; j++){
				ll c=0;
				for(int l=j+1; l<=i; l++){
					c+=max(0, i-V[l]);
				}
				dp[i][kk]=min(dp[i][kk], dp[j][kk-1]+c);
			}
		}
	}
	cout<<dp[n][k];
}

Subtask #1

16.0 / 16.0

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

Subtask #2

24.0 / 24.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	0 ms	212 KB	Output is correct
10	Correct	0 ms	212 KB	Output is correct
11	Correct	1 ms	212 KB	Output is correct
12	Correct	1 ms	212 KB	Output is correct
13	Correct	1 ms	304 KB	Output is correct
14	Correct	1 ms	300 KB	Output is correct
15	Correct	1 ms	212 KB	Output is correct
16	Correct	0 ms	300 KB	Output is correct
17	Correct	41 ms	364 KB	Output is correct
18	Correct	1355 ms	680 KB	Output is correct
19	Correct	3740 ms	1380 KB	Output is correct
20	Correct	15 ms	340 KB	Output is correct
21	Correct	29 ms	212 KB	Output is correct
22	Correct	5569 ms	2280 KB	Output is correct
23	Correct	5334 ms	2276 KB	Output is correct
24	Correct	145 ms	352 KB	Output is correct
25	Correct	5483 ms	2272 KB	Output is correct
26	Correct	5053 ms	1940 KB	Output is correct
27	Correct	2388 ms	1064 KB	Output is correct
28	Correct	2374 ms	980 KB	Output is correct

Subtask #3

0 / 21.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	0 ms	212 KB	Output is correct
10	Correct	0 ms	212 KB	Output is correct
11	Correct	1 ms	212 KB	Output is correct
12	Correct	1 ms	212 KB	Output is correct
13	Correct	1 ms	304 KB	Output is correct
14	Correct	1 ms	300 KB	Output is correct
15	Correct	1 ms	212 KB	Output is correct
16	Correct	0 ms	300 KB	Output is correct
17	Correct	41 ms	364 KB	Output is correct
18	Correct	1355 ms	680 KB	Output is correct
19	Correct	3740 ms	1380 KB	Output is correct
20	Correct	15 ms	340 KB	Output is correct
21	Correct	29 ms	212 KB	Output is correct
22	Correct	5569 ms	2280 KB	Output is correct
23	Correct	5334 ms	2276 KB	Output is correct
24	Correct	145 ms	352 KB	Output is correct
25	Correct	5483 ms	2272 KB	Output is correct
26	Correct	5053 ms	1940 KB	Output is correct
27	Correct	2388 ms	1064 KB	Output is correct
28	Correct	2374 ms	980 KB	Output is correct
29	Execution timed out	7008 ms	79304 KB	Time limit exceeded
30	Halted	0 ms	0 KB	-

Subtask #4

0 / 26.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	0 ms	212 KB	Output is correct
10	Correct	0 ms	212 KB	Output is correct
11	Correct	1 ms	212 KB	Output is correct
12	Correct	1 ms	212 KB	Output is correct
13	Correct	1 ms	304 KB	Output is correct
14	Correct	1 ms	300 KB	Output is correct
15	Correct	1 ms	212 KB	Output is correct
16	Correct	0 ms	300 KB	Output is correct
17	Correct	41 ms	364 KB	Output is correct
18	Correct	1355 ms	680 KB	Output is correct
19	Correct	3740 ms	1380 KB	Output is correct
20	Correct	15 ms	340 KB	Output is correct
21	Correct	29 ms	212 KB	Output is correct
22	Correct	5569 ms	2280 KB	Output is correct
23	Correct	5334 ms	2276 KB	Output is correct
24	Correct	145 ms	352 KB	Output is correct
25	Correct	5483 ms	2272 KB	Output is correct
26	Correct	5053 ms	1940 KB	Output is correct
27	Correct	2388 ms	1064 KB	Output is correct
28	Correct	2374 ms	980 KB	Output is correct
29	Execution timed out	7008 ms	79304 KB	Time limit exceeded
30	Halted	0 ms	0 KB	-

Subtask #5

0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	0 ms	212 KB	Output is correct
10	Correct	0 ms	212 KB	Output is correct
11	Correct	1 ms	212 KB	Output is correct
12	Correct	1 ms	212 KB	Output is correct
13	Correct	1 ms	304 KB	Output is correct
14	Correct	1 ms	300 KB	Output is correct
15	Correct	1 ms	212 KB	Output is correct
16	Correct	0 ms	300 KB	Output is correct
17	Correct	41 ms	364 KB	Output is correct
18	Correct	1355 ms	680 KB	Output is correct
19	Correct	3740 ms	1380 KB	Output is correct
20	Correct	15 ms	340 KB	Output is correct
21	Correct	29 ms	212 KB	Output is correct
22	Correct	5569 ms	2280 KB	Output is correct
23	Correct	5334 ms	2276 KB	Output is correct
24	Correct	145 ms	352 KB	Output is correct
25	Correct	5483 ms	2272 KB	Output is correct
26	Correct	5053 ms	1940 KB	Output is correct
27	Correct	2388 ms	1064 KB	Output is correct
28	Correct	2374 ms	980 KB	Output is correct
29	Execution timed out	7008 ms	79304 KB	Time limit exceeded
30	Halted	0 ms	0 KB	-