SHARE
TWEET

Untitled

a guest May 25th, 2019 72 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define int int64_t
  6. #define F(i, n) for(int i = 0; i < n; ++ i)
  7.  
  8. int n, T, cnt = 0, lst_dom;
  9. string str;
  10. vector<int> v;
  11.  
  12. int check(int m) {
  13.     string s = str;
  14.     int ans2 = INT_MAX;
  15.     int ans = 0, rem = cnt, tec = cnt - m;
  16.     F(i, n) {
  17.         if(!rem) break;
  18.         if(s[i] == 'D') {
  19.             if(!tec) {
  20.                 int pos = max(v[m - 1], lst_dom);
  21.                 ans2 = ans + (pos - i) * 2;
  22.                 for(int j = i + 1; j <= v[m - 1]; ++ j) {
  23.                     if(s[j] == 'M') {
  24.                         ++ tec;
  25.                         s[j] = '.';
  26.                     }
  27.                     if(s[j] == 'D') {
  28.                         -- tec;
  29.                         s[j] = '.';
  30.                         -- rem;
  31.                     }
  32.                     ans += 2;
  33.                 }
  34.             }
  35.             -- tec;
  36.             -- rem;
  37.         }
  38.         if(str[i] == 'M') ++ tec;
  39.         if(!rem) break;
  40.         ++ ans;
  41.     }
  42.     return min(ans, ans2);
  43. }
  44.  
  45. int32_t main() {
  46.     ios_base::sync_with_stdio(false);
  47.     cin >> n >> T >> str;
  48.     str = '.' + str; ++ n;
  49.     F(i, n) {
  50.         if(str[i] == 'M') v.push_back(i);
  51.         if(str[i] == 'D') {
  52.             ++ cnt;
  53.             lst_dom = i;
  54.         }
  55.     }
  56.     int l = 0, r = v.size() + 1;
  57.     while(l < r) {
  58.         int m = (l + r) / 2;
  59.         if(check(m) <= T) {
  60.             l = m + 1;
  61.         } else r = m;
  62.     }
  63.     if(!l) {
  64.         cout << -1;
  65.         return 0;
  66.     }
  67.     cout << cnt - l + 1;
  68. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top