Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- #define ll long long
- #define vi vector<ll>
- #define vll vector<long long ll>
- int main()
- {
- #ifndef ONLINE_JUDGE
- freopen("in.txt","r",stdin);
- freopen("out.txt","w",stdout);
- #endif
- std::ios::sync_with_stdio(false);
- ll t;
- cin >> t;
- while (t--)
- {
- ll n, k;
- cin >> n >> k;
- string s;
- cin >> s;
- vector<ll> Left_counter(n), Right_counter(n);
- ll cnt = 0, cnt1 = 0;
- bool counter_present = false;
- for (ll i = 0; i < n; ++i)
- {
- if (s[i] == '1')
- {
- counter_present = true;
- cnt = 0;
- Left_counter[i] = 0;
- }
- else if (counter_present)
- {
- cnt++;
- Left_counter[i] = cnt;
- }
- else
- Left_counter[i] = ll_MAX;
- }
- counter_present = false;
- for (ll i = n - 1; i >= 0; --i)
- {
- if (s[i] == '1')
- {
- counter_present = true;
- cnt = 0;
- Right_counter[i] = 0;
- }
- else if (counter_present)
- {
- cnt++;
- Right_counter[i] = cnt;
- }
- else
- Right_counter[i] = ll_MAX;
- }
- ll cost = 0;
- for (ll i = 0; i < n; ++i)
- {
- if (s[i] != '1')
- {
- cost += min(Left_counter[i], Right_counter[i]);
- }
- cost += k;
- }
- cout << cost << endl;
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement