fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int n, k, ans, noww, a[220], s[220], f[220][220][33];
  5.  
  6. void maximize(int &a, int b) {
  7. 	if (a < b) a = b;
  8. }
  9.  
  10. int dp(int i, int j, int u) {
  11. 	if (u >= k) return 0;
  12. 	if (i > j) return 1;
  13. 	int rs = f[i][j][u];
  14. 	if (rs != -1) return rs;
  15. 	maximize(rs, 1 - dp(i + 1, j, noww - (u + a[i]) -  (s[j] - s[i])));
  16. 	maximize(rs, 1 - dp(i, j - 1, noww - (u + a[j]) - (s[j - 1] - s[i - 1])));
  17. 	return f[i][j][u] = rs;
  18. }
  19.  
  20. int32_t main() {
  21. 	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  22.  
  23. 	cin >> n >> k;
  24. 	for(int i = 1; i <= n; i++) {
  25. 		char c;
  26. 		cin >> c;
  27. 		a[i] = a[i + n] = (c == 'B');
  28. 	}
  29.  
  30. 	for(int i = 1; i <= 2 * n; i++) s[i] = s[i - 1] + a[i];
  31.  
  32. 	memset(f, -1, sizeof f);
  33. 	for(int i = 1; i <= n; i++) {
  34. 		noww = s[i + n - 1] - s[i - 1];
  35. 		ans += dp(i, i + n - 1, 0);
  36. 	}
  37.  
  38. 	cout << ans;
  39. }
Success #stdin #stdout 0.01s 9984KB
comments (?)
stdin
copy 
8 1
BRBRRBRR
stdout
copy 
2
https://ideone.com/pTa2ac
language:
C++14 (gcc 8.3)
created:
1 year ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!