newb_ie

Untitled

Sep 19th, 2021 (edited)
197
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.37 KB | None | 0 0
  1. #include "bits/stdc++.h"
  2. using namespace std;
  3.  
  4. const int N = 100010;
  5. int n,k; //n = number of characters and k = how many character's you can change
  6. int pa[N],pb[N]; //pa => prefix sum of a,pb => pref sum of b
  7.  
  8. bool yes (int x) {
  9. int L = 1,R = x;
  10. while (R <= n) {
  11. int a = pa[R] - pa[L - 1];
  12. int b = pb[R] - pb[L - 1];
  13. int m = min(a,b);
  14. if (m <= k) {
  15. //~ cout << L << ' ' << R << '\n';
  16. return true;
  17. }
  18. L++,R++;
  19. }
  20. //asbei na
  21. return false;
  22. }
  23.  
  24. //1) calc pref
  25. //2) bin search
  26. //3) implement yes function
  27.  
  28. int main () {
  29. ios::sync_with_stdio(false);
  30. cin.tie(nullptr);
  31. cout.tie(nullptr);
  32. string s;
  33. cin >> n >> k >> s;
  34. int a[n + 1],b[n + 1];//if ith pos contain a 1 otherwise 0
  35. a[0] = 0,b[0] = 0;
  36. for (int i = 0; i < n; ++i) {
  37. if (s[i] == 'a') {
  38. a[i + 1] = 1;
  39. } else {
  40. a[i + 1] = 0;
  41. }
  42. }
  43. for (int i = 0; i < n; ++i) {
  44. if (s[i] == 'b') {
  45. b[i + 1] = 1;
  46. } else {
  47. b[i + 1] = 0;
  48. }
  49. }
  50. for (int i = 1; i <= n; ++i) {
  51. pa[i] = pa[i - 1] + a[i];
  52. }
  53. for (int i = 1; i <= n; ++i) {
  54. pb[i] = pb[i - 1] + b[i];
  55. }
  56. int l = 1,r = n;
  57. int res = 0;
  58. while (l <= r) {
  59. int mid = (l + r) / 2;
  60. if (yes(mid)) {
  61. res = mid;
  62. l = mid + 1;
  63. } else {
  64. r = mid - 1;
  65. }
  66. }
  67. cout << res << '\n';
  68. }
  69.  
  70. //Problem Link : https://codeforces.com/contest/676/problem/C
Add Comment
Please, Sign In to add comment