DuongNhi99

MONOTONE

Dec 16th, 2020
115
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.86 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #define ll long long
  3. using namespace std;
  4.  
  5. const int N = 1e6 + 5;
  6.  
  7. ll n, c;
  8. string s;
  9.  
  10. int main() {
  11.     freopen("MONOTONE.inp", "r", stdin);
  12.     freopen("MONOTONE.out", "w", stdout);
  13.     ios_base::sync_with_stdio(false);
  14.     cin.tie(NULL); cout.tie(NULL);
  15.  
  16.     cin >> n >> c >> s;
  17.  
  18.     ll inca = 0, incb = 0, ab = 0;
  19.     ll ans = 0;
  20.  
  21.     ll j = 0;
  22.     for(ll i = 0; i < n; ++i) {
  23.         while(j < n && ab <= c) {
  24.             ans = max(ans, (j - i) * 1LL);
  25.  
  26.             if(s[j] == 'a')
  27.                 ++inca;
  28.             else if(s[j] == 'b')
  29.                 ++incb, ab += inca;
  30.  
  31.             ++j;
  32.         }
  33.  
  34.         if(ab <= c) ans = max(ans, (j - i) * 1LL);
  35.  
  36.         if(s[i] == 'b')
  37.             --incb;
  38.         else if(s[i] == 'a')
  39.             --inca, ab -= incb;
  40.     }
  41.  
  42.     cout << ans << '\n';
  43.  
  44.     return 0;
  45. }
  46.  
Advertisement
Add Comment
Please, Sign In to add comment