fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define int long long
  5. #define ll long long
  6. typedef vector<int> vi;
  7. #define F first;
  8. #define S second;
  9. #define sz(x) x.size()
  10. #define all(x) (x).begin(), (x).end()
  11. #define rall(x) (x).rbegin(), (x).rend()
  12. #define allr(x) (x).rbegin(), (x).rend()
  13. #define pb push_back
  14. #define endl "\n"
  15. #define YES cout << "YES\n"
  16. #define NO cout << "NO\n"
  17.  
  18. void solve() {
  19.     ll n, k; cin >> n >> k;
  20.     ll wh = 0;
  21.     string s; cin >> s;
  22.     s += '1';
  23.     vector<ll> vp, vp2;
  24.     ll l = 0;
  25.     set<char> se;
  26.     for (int i = 0; i < n; i++) {
  27.         se.insert(s[i]);
  28.     }   
  29.     if (sz(se) == 1) {
  30.         cout << 0 << endl;
  31.         return;
  32.     }
  33.     for (int i = 0; i < n; i++) {
  34.         if (s[i] == '1' && s[i + 1] == '0') l = i + 1;
  35.         if (s[i] == '0' && s[i + 1] == '1') {
  36.             ll si = i - l + 1;
  37.             if (l != 0 && i != n - 1) {
  38.                 wh += 2;
  39.                 vp.pb(si);
  40.             } else {
  41.                 wh += 1;
  42.                 vp2.pb(si);
  43.             }
  44.         }
  45.     }
  46.     sort(all(vp));
  47.     sort(all(vp2));
  48.     for (auto e : vp) {
  49.         if (k >= e) {
  50.             k -= e;
  51.             wh -= 2;
  52.         }
  53.     }
  54.     for (auto e : vp2) {
  55.         if (k >= e) {
  56.             k -= e;
  57.             wh -= 1;
  58.         }
  59.     }
  60.     cout << wh << endl;
  61. }
  62.  
  63.  
  64. int32_t main() {
  65.     ios_base::sync_with_stdio(false);
  66.     cin.tie(0);
  67.     #ifndef ONLINE_JUDGE
  68.         freopen("in.txt", "r", stdin);
  69.         freopen("out.txt", "w", stdout);
  70.     #endif
  71.     freopen("strips.in", "r", stdin);
  72.     //freopen("wtf.out", "w", stdout);
  73.     int t = 1;
  74.     cin >> t;
  75.  
  76.     while(t--) {
  77.         solve();
  78.     }
  79. }
Success #stdin #stdout 0.01s 5328KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/96JYto
language:
C++ (gcc 8.3)
created:
1 day 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!