Submission #1349270

#TimeUsernameProblemLanguageResultExecution timeMemory
1349270sigmaligmaJJOOII 2 (JOI20_ho_t2)C++20
100 / 100
7 ms3888 KiB
#include <bits/stdc++.h>
using namespace std;

#define fastio                   \
    ios::sync_with_stdio(false); \
    cin.tie(nullptr);
#define s(x) x.size()
#define sort(x) sort(x.begin(), x.end())
#define rsort(x) sort(x.rbegin(), x.rend())
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define fi first
#define se second
#define INF 1e9
#define INFL 1e18
#define rep(a, b) for (int a = 0; a < b; a++)

using ll = long long;
using pii = pair<int, int>;

void solve()
{
    int n, k;
    string s;
    cin >> n >> k >> s;
    int l = 0, p = 0;
    vector<int> dpj(n, -1);
    int suma = 0;
    while (p < n)
    {
        if (s[p] == 'J')
            suma++;
        while (suma > k || s[l] != 'J')
        {
            if (s[l] == 'J')
                suma--;
            l++;
        }
        if (suma == k)
            dpj[p] = p - l + 1 - k;
        p++;
    }
    l = 0, p = 0;
    vector<pair<int, int>> dpo(n, {-1, -1});
    suma = 0;
    while (p < n)
    {
        if (s[p] == 'O')
            suma++;
        while (suma > k || s[l] != 'O')
        {
            if (s[l] == 'O')
                suma--;
            l++;
        }
        if (suma == k)
            dpo[p] = {l, p - l + 1 - k};
        p++;
    }
    l = n - 1, p = n - 1;
    vector<int> dpi(n, -1);
    suma = 0;
    while (p >= 0)
    {
        if (s[p] == 'I')
            suma++;
        while (suma > k || s[l] != 'I')
        {
            if (s[l] == 'I')
                suma--;
            l--;
        }
        if (suma == k)
            dpi[p] = l - p + 1 - k;
        p--;
    }

    int minn = 1e9;
    // for (int i = 0; i < n; i++)
    // {
    //     cout << dpj[i] << ' ';
    // }
    // cout << endl;
    // for (int i = 0; i < n; i++)
    // {
    //     cout << dpo[i].second << ' ';
    // }
    // cout << endl;
    // for (int i = 0; i < n; i++)
    // {
    //     cout << dpi[i] << ' ';
    // }
    // cout << endl;
    for (int i = 1; i < n - 1; i++)
    {
        if (dpo[i].first > 0)
            if (dpj[dpo[i].first-1] != -1 && dpo[i].first != -1 && dpi[i + 1] != -1)
                minn = min(minn, dpj[dpo[i].first-1] + dpo[i].second + dpi[i + 1]);
    }
    if (minn != 1e9)
        cout << minn << endl;
    else
        cout << -1 << endl;
}

int main()
{
    fastio;
    int t = 1;
    // cin >> t;
    while (t--)
        solve();
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...