Competitive Programming Solutions

1367C - Social Distance

13 Jan 2021 — Tags: greedy,implementation — URL

For each block of consecutive zeros (with one on both ends) of size $m$, one can place $ceil(\frac{m - 2k}{k + 1})$ ones.

Time complexity: $O(n)$

Memory complexity: $O(n)$

Click to show code.

 

using namespace std;
using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
int ceil(int a, int b) { return (a + b - 1) / b; }
int solve(string s, int k)
{
    s = "1" + string(k, '0') + s + string(k, '0') + "1";
    int cnt = 0;
    vi lengths;
    for (auto c : s)
    {
        if (c == '0')
            ++cnt;
        else
        {
            lengths.push_back(max(cnt - 2 * k, 0));
            cnt = 0;
        }
    }
    return accumulate(begin(lengths), end(lengths), 0LL, [k](int acc, int x) {
        return acc + ceil(x, k + 1);
    });
}
int main(void)
{
    ios::sync_with_stdio(false), cin.tie(NULL);
    int t;
    cin >> t;
    while (t--)
    {
        int n, k;
        string s;
        cin >> n >> k >> s;
        cout << solve(s, k) << endl;
    }
    return 0;
}

Related posts