oj.uz

Submission #834703

# Submission time Handle Problem Language Result Execution time Memory
834703 2023-08-22T17:24:58 Z Antekb Chorus (JOI23_chorus) C++17
40 / 100
 7000 ms 79316 KB 
#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++){
			ll c=0;
			for(int j=i-1; j>=0; j--){
				c+=max(0, i-V[j+1]);
				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 1 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 0 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 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 212 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 1 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 0 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 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 16 ms 596 KB Output is correct
19 Correct 42 ms 1376 KB Output is correct
20 Correct 1 ms 212 KB Output is correct
21 Correct 1 ms 212 KB Output is correct
22 Correct 61 ms 2260 KB Output is correct
23 Correct 59 ms 2260 KB Output is correct
24 Correct 2 ms 340 KB Output is correct
25 Correct 61 ms 2272 KB Output is correct
26 Correct 70 ms 1936 KB Output is correct
27 Correct 27 ms 964 KB Output is correct
28 Correct 27 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 1 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 0 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 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 16 ms 596 KB Output is correct
19 Correct 42 ms 1376 KB Output is correct
20 Correct 1 ms 212 KB Output is correct
21 Correct 1 ms 212 KB Output is correct
22 Correct 61 ms 2260 KB Output is correct
23 Correct 59 ms 2260 KB Output is correct
24 Correct 2 ms 340 KB Output is correct
25 Correct 61 ms 2272 KB Output is correct
26 Correct 70 ms 1936 KB Output is correct
27 Correct 27 ms 964 KB Output is correct
28 Correct 27 ms 980 KB Output is correct
29 Execution timed out 7042 ms 79316 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 1 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 0 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 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 16 ms 596 KB Output is correct
19 Correct 42 ms 1376 KB Output is correct
20 Correct 1 ms 212 KB Output is correct
21 Correct 1 ms 212 KB Output is correct
22 Correct 61 ms 2260 KB Output is correct
23 Correct 59 ms 2260 KB Output is correct
24 Correct 2 ms 340 KB Output is correct
25 Correct 61 ms 2272 KB Output is correct
26 Correct 70 ms 1936 KB Output is correct
27 Correct 27 ms 964 KB Output is correct
28 Correct 27 ms 980 KB Output is correct
29 Execution timed out 7042 ms 79316 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 1 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 0 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 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 16 ms 596 KB Output is correct
19 Correct 42 ms 1376 KB Output is correct
20 Correct 1 ms 212 KB Output is correct
21 Correct 1 ms 212 KB Output is correct
22 Correct 61 ms 2260 KB Output is correct
23 Correct 59 ms 2260 KB Output is correct
24 Correct 2 ms 340 KB Output is correct
25 Correct 61 ms 2272 KB Output is correct
26 Correct 70 ms 1936 KB Output is correct
27 Correct 27 ms 964 KB Output is correct
28 Correct 27 ms 980 KB Output is correct
29 Execution timed out 7042 ms 79316 KB Time limit exceeded
30 Halted 0 ms 0 KB -