제출 #1211684

#제출 시각아이디문제언어결과실행 시간메모리
1211684dima2101JJOOII 2 (JOI20_ho_t2)C++20
0 / 100
0 ms320 KiB
#include <bits/stdc++.h>

#define int long long

int give_sum(int l, int r, std::vector<int> &pref)
{
    if (l > r)
    {
        std::swap(l, r);
    }
    if (l == 0)
    {
        return pref[r];
    }
    return pref[r] - pref[l - 1];
}

signed main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    int n, k;
    std::cin >> n >> k;

    std::string s;
    std::cin >> s;

    std::vector<int> prev_j(n);
    std::vector<int> next_i(n);
    std::vector<int> pref_j(n);
    std::vector<int> pref_i(n);
    std::vector<int> pref_o(n);
    pref_j[0] = (s[0] == 'J');
    pref_i[0] = (s[0] == 'I');
    pref_o[0] = (s[0] == 'O');
    int last_j = -1;
    for (int i = 0; i < n; i++)
    {
        if (s[i] == 'J')
        {
            last_j = i;
        }
        prev_j[i] = last_j;
        pref_j[i] = pref_j[i - 1] + (s[i] == 'J');
        pref_i[i] = pref_i[i - 1] + (s[i] == 'I');
        pref_o[i] = pref_o[i - 1] + (s[i] == 'O');
    }

    int last_i = -1;
    for (int i = n - 1; i >= 0; i--)
    {
        if (s[i] == 'I')
        {
            last_i = i;
        }
        next_i[i] = last_i;
    }
    int ans = 1e9;
    for (int i = 0; i < n; i++)
    {
        if (s[i] != 'O')
            continue;

        int l = i - 1, r = n;
        while (l + 1 < r)
        {
            int mid = (l + r) / 2;

            if (give_sum(i, mid, pref_o) < k)
            {
                l = mid;
            }
            else
            {
                r = mid;
            }
        }

        if (r == n)
        {
            continue;
        }

        int start = i;
        int stop = r;
        int now = (stop - start + 1) - k;

        int tmp = prev_j[i];

        if (tmp == -1)
        {
            continue;
        }
        now += (start - tmp - 1);

        l = -1, r = tmp;
        while (l + 1 < r)
        {
            int mid = (l + r) / 2;
            if (give_sum(mid, tmp, pref_j) < k)
            {
                r = mid;
            }
            else
            {
                l = mid;
            }
        }

        if (l == -1)
        {
            continue;
        }
        now += (std::abs(tmp - l) + 1) - k;

        tmp = next_i[stop];
        if (tmp == -1)
        {
            continue;
        }

        now += (std::abs(stop - tmp) - 1);

        l = tmp - 1,
        r = n;
        while (l + 1 < r)
        {
            int mid = (l + r) / 2;
            if (give_sum(tmp, mid, pref_i) < k)
            {
                l = mid;
            }
            else
            {
                r = mid;
            }
        }
        if (r == n)
        {
            continue;
        }
        // std::cout << now << ' ' << r << ' ' << tmp << std::endl;
        now += (r - tmp + 1) - k;
        // std::cout << now << std::endl;
        ans = std::min(ans, now);
    }
    if (ans == 1e9)
    {
        std::cout << -1;
        return 0;
    }
    std::cout << ans;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...