fork download
copy 
  1. //...START BY DOING WHAT IS NECESSARY, THEN WHAT IS POSSIBLE AND SUDDENLY YOU ARE DOING THE IMPOSSIBLE... 
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4. #define FAST_FURIER ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
  5. #define pb push_back
  6. #define rep(i,a,N) for(ll i=a;i<N;i++)
  7. typedef long long ll;
  8. #define endl '\n'
  9. #define M 1000000007
  10. bool comp(int x,int y)
  11. {
  12.     return x > y;   
  13. }
  14.  
  15.  
  16. /*..............................code starts here........................*/
  17. // S is the courage to continue that counts.
  18.  
  19. int main() {
  20.     FAST_FURIER;
  21.     int t=1;
  22.     cin >> t;
  23.     ll m,n,k;
  24.     string a,b;
  25.     while(t--)  
  26.     {
  27.         cin >> n >> k >> a;
  28.         int zero = 0;
  29.         int flag = 0;
  30.         int start = 0,end = n-1,s1 = 0,s2 = 0;
  31.  
  32.         if(!(a[0]-'0')){
  33.             rep(i,0,n){
  34.                 if(a[i]=='1'){
  35.                     start = i;
  36.                     break;
  37.                 }
  38.                 else s1 += 1;
  39.                 start = i+1;
  40.             }
  41.         }
  42.         if(!(a[n-1]-'0')){
  43.             for(int i=n-1;i>-1;i--){
  44.                 if(a[i]=='1'){
  45.                     end = i;
  46.                     break;
  47.                 }
  48.                 else s2 += 1;
  49.                 end = i-1;
  50.             }
  51.         }
  52.         if(start == n and end == -1){
  53.             cout <<0 << endl;
  54.             continue;
  55.         }
  56.         if(!k){
  57.             int zero = 0;
  58.             rep(i,0,n){
  59.                 if(!(a[i]-'0')) ++zero;
  60.             }
  61.             cout << zero << endl;
  62.  
  63.             continue;
  64.         }
  65.         //cout << s1 << " " << s2 << endl;
  66.  
  67.         vector<int>vec;
  68.         int s=-1;
  69.         rep(i,start,end+1){
  70.             if(!(a[i]-'0')){
  71.                 if(!flag){
  72.                     start = i;
  73.                     flag = 1;
  74.                 }
  75.             }
  76.             else{
  77.                 if(flag){
  78.                     vec.pb(i-start);
  79.                     flag = 0;
  80.                 }
  81.             }
  82.         }
  83.         sort(vec.begin(),vec.end());
  84.         //rep(i,0,vec.size()) cout << vec[i] << " ";
  85.         //cout << endl;
  86.         while(k>0 and vec.size()){
  87.            // cout << vec.size() <<" " << vec.back() <<  endl;
  88.             if(!(s1+s2) and k == 1)
  89.             break;
  90.             if(vec.back() <= s1 or vec.back() <= s2){
  91.                 if(s2 >= s1){
  92.                     k -= 1;
  93.                     s2 =0;
  94.                 }
  95.                 else{
  96.                     k -= 1;
  97.                     s1 = 0;
  98.                 }
  99.             }
  100.             else{
  101.                 if(k > 1){
  102.                     k -= 2;
  103.                     vec.pop_back();
  104.                 }
  105.                 else {
  106.                     if(s1 >= s2) s1 =0;
  107.                     else s2 = 0;
  108.                 }
  109.             }
  110.             //cout << "k " << k << endl;
  111.         }
  112.         if(vec.size() == 0 and (s1+s2) != 0 and k != 0){
  113.             if(k > 1){
  114.                 s1 = 0;
  115.                 s2 = 0;
  116.             }
  117.             else if(k == 1){
  118.                 if(s1 >= s2) s1 = 0;
  119.                 else s2 = 0;
  120.             }
  121.         }
  122.         if(!vec.size() and !(s1+s2)) cout << 0 << endl;
  123.         else{
  124.  
  125.             int sum = 0;
  126.             rep(i,0,vec.size()){
  127.                 sum += vec[i];
  128.             }
  129.             cout << sum +s1+s2<< endl;
  130.         }
  131.     }
  132. }
  133.  
  134.  
  135.  
  136.  
  137. // Author : shihack
  138.  
  139. // g++ -std=c++17
Runtime error #stdin #stdout 0s 4504KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/E77cDl
language:
C++ (gcc 8.3)
created:
3 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!