fork download
copy 
  1. #include <cstdio>
  2. #include <vector>
  3.  
  4.  
  5. void p(std::vector<int> const & dp) {
  6. 	for (auto a : dp) {
  7. 		printf("%d ", a);
  8. 	}
  9. 	printf("\n");
  10. }
  11.  
  12. int main() {
  13.     int l, k, res = 0;
  14.     char s[5432];
  15.  
  16.     scanf("%d %d", &l, &k);
  17.     scanf("%s", s);
  18.  
  19.     std::vector<int> dp1(l, 0), dp2(l, 0), dp3(l, 0);
  20.  
  21.     for (int len = 1; len <= l; ++len) {
  22.         for (int i = 0; i + len - 1 < l; ++i) {
  23.             int last = i + len - 1;
  24.             if (len == 1) {
  25.                 dp1[i] = 0;
  26.                 res += 1;
  27.                 printf("1: %d %c %d\n", i, s[i], dp1[i]);
  28.             }
  29.             else if (len == 2) {
  30.                 if (s[i] == s[last]) {
  31.                     dp2[i] = 0;
  32.                 }
  33.                 else {
  34.                     dp2[i] = 1;
  35.                 }
  36.                 printf("2: %d %c %d\n", i, s[i], dp2[i]);
  37.                 if (dp2[i] <= k) {
  38.                    res += 1;
  39.                 }
  40.             }
  41.             else {
  42.             	p(dp1); p(dp2); p(dp3);
  43.             	printf("%d %c %c %d\n", len, s[i], s[last], dp1[i + 1]);
  44.                 if (s[i] == s[last]) {
  45.                     dp3[i] = dp1[i + 1];
  46.                 }
  47.                 else {
  48.                     dp3[i] = 1 + dp1[i + 1];
  49.                 }
  50.               if (dp3[i] <= k) {
  51.                 res += 1;
  52.               }
  53.  
  54.             }
  55.  
  56.         }
  57.         if (len >= 3) {
  58.         	dp1.clear();
  59.               dp1 = dp2;
  60.               dp2.clear();
  61.               dp2 = dp3;
  62.               dp3.clear();
  63.         }
  64.         printf("%d\n", res);
  65.  
  66.     }
  67.  
  68.     printf("%d\n", res);
  69.  
  70.     return 0;
  71. }
  72.  
  73.  
Success #stdin #stdout 0s 4468KB
comments (?)
stdin
copy 
5 1
abcde
stdout
copy 
1: 0 a 0
1: 1 b 0
1: 2 c 0
1: 3 d 0
1: 4 e 0
5
2: 0 a 1
2: 1 b 1
2: 2 c 1
2: 3 d 1
9
0 0 0 0 0 
1 1 1 1 0 
0 0 0 0 0 
3 a c 0
0 0 0 0 0 
1 1 1 1 0 
1 0 0 0 0 
3 b d 0
0 0 0 0 0 
1 1 1 1 0 
1 1 0 0 0 
3 c e 0
12
1 1 1 1 0 
1 1 1 0 0 

4 a d 1
1 1 1 1 0 
1 1 1 0 0 

4 b e 1
12
1 1 1 0 0 


5 a e 1
12
12
https://ideone.com/aB3ppk
language:
C++14 (gcc 8.3)
created:
4 years 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!