1691C - Sum of Substrings - CodeForces Solution

#include<bits/stdc++.h>
using namespace std;
#define fast ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define pb push_back
#define vi vector<int>
#define vl vector<ll>
#define vc vector
#define imax INT_MAX
#define imin INT_MIN
#define ff first
#define ss second
#define all(x) (x).begin() , (x).end()
#define rall(x) (x).rbegin() , (x).rend()
#define cu continue
#define endl "\n"

typedef long long ll;
typedef unsigned long long ull;
typedef long double lld;
const ll mod = 1e9 + 7;

#ifndef ONLINE_JUDGE
#define debug(x) cerr << #x <<" "; _print(x); cerr << endl;
#else
#define debug(x);
#endif

void _print(ll t) {cerr << t;}
void _print(int t) {cerr << t;}
void _print(string t) {cerr << t;}
void _print(char t) {cerr << t;}
void _print(lld t) {cerr << t;}
void _print(double t) {cerr << t;}
void _print(ull t) {cerr << t;}
 
template <class T, class V> void _print(pair <T, V> p);
template <class T> void _print(vector <T> v);
template <class T> void _print(set <T> v);
template <class T, class V> void _print(map <T, V> v);
template <class T> void _print(multiset <T> v);
template <class T, class V> void _print(pair <T, V> p) {cerr << "{"; _print(p.ff); cerr << ","; _print(p.ss); cerr << "}";}
template <class T> void _print(vector <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T> void _print(set <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T> void _print(multiset <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T, class V> void _print(map <T, V> v) {cerr << "[ "; for (auto i : v) {_print(i); cerr << " ";} cerr << "]";}

// FUNCTIONS //
ll mod_mul(ll a, ll b) {a = a % mod; b = b % mod; return (((a * b) % mod) + mod) % mod;} 
ll mod_add(ll a, ll b) {a = a % mod; b = b % mod; return (((a + b) % mod) + mod) % mod;} 
ll gcd(ll a, ll b) { if (b == 0) return a; return gcd(b, a % b);}
ll ceil_div(ll a, ll b) {return a % b == 0 ? a / b : a / b + 1;}

/*----------------------------------------------------------------------------------------------------------------------------*/

void read(){
    fast;
    #ifndef ONLINE_JUDGE
    freopen("Error.txt", "w", stderr);
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif // ONLINE_JUDGE
}

int main()
{
    read();

    int t = 1;
    cin >> t;

    while(t--){
        int n , k;
        cin >> n >> k;

        string s;
        cin >> s;

        
        int first = INT_MAX , last = INT_MIN;
        for(int i = 0 ; i < n ; i++){
            if(s[i] == '1'){
                first = min(i , first);
                last = max(i , last);
            }
        }

        if(first == INT_MAX and last == INT_MIN){
            cout<<0<<endl;
            cu;
        }

        
        if(n - 1 - last <= k){
            s[last] = '0';
            s[n - 1] = '1';
            k -= n - 1 - last;
        }

        if(first <= k and s[first] == '1' and first != n - 1){
            s[first] = '0';
            s[0] = '1';
        }


        ll ans = 0;
        for(int i = 0 ; i < n - 1 ; i++){
            if(s[i] == '1'){
                if(s[i + 1] == '0')
                    ans += 10;
                else
                    ans += 11;
            }
            else if(s[i + 1] == '1'){
                ans++;
            }
        }
        cout<<ans<<endl;
    }
    
    return 0;
}