Submission #1183355

#	Time	Username	Problem	Language	Result	Execution time	Memory
1183355		zyntherix	JJOOII 2 (JOI20_ho_t2)	C++20	100 / 100	11 ms	3024 KiB

ho_t2

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pi pair<int, int>
#define vi vector<int>
#define vs vector<string>
#define vb vector<bool>
#define vpi vector<pi>
#define pb push_back
#define all(a) (a).begin(), (a).end()
const int mod = 1e9 + 7;
vi j, o, i;
int n, k;
string s;

int f(int st)
{
    int curr = j[(st + k) - 1];
    int ans = ((curr - j[st]) + 1) - k;
    auto n_os = upper_bound(o.begin(), o.end(), curr);
    if (o.end() - n_os < k)
        return mod;
    auto n_oe = n_os;
    n_oe += (k - 1);
    ans += (*n_os - curr) - 1;
    ans += ((*n_oe - *n_os) + 1) - k;
    auto n_is = upper_bound(i.begin(), i.end(), *n_oe);
    if (i.end() - n_is < k)
        return mod;
    auto n_ie = n_is;
    n_ie += (k - 1);
    ans += (*n_is - *n_oe) - 1;
    ans += ((*n_ie - *n_is) + 1) - k;
    return ans;
}

signed main()
{
    cin >> n >> k >> s;
    for (int x = 0; x < n; x++)
    {
        if (s[x] == 'J')
        {
            j.pb(x);
        }
        if (s[x] == 'O')
        {
            o.pb(x);
        }
        if (s[x] == 'I')
        {
            i.pb(x);
        }
    }
    int ans = mod;
    for (int x = 0; x <= j.size() - k; x++)
    {
        ans = min(ans, f(x));
    }
    cout << (ans == mod ? -1 : ans) << '\n';
}

• Subtask 1: 1 / 1
• Subtask 2: 12 / 12
• Subtask 3: 87 / 87