Submission #832779

#TimeUsernameProblemLanguageResultExecution timeMemory
832779OAleksaJJOOII 2 (JOI20_ho_t2)C++14
100 / 100
9 ms3300 KiB
#include <bits/stdc++.h>
#define f first
#define s second
#define int long long
using namespace std;

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, k;
    string s;
    cin >> n >> k >> s;
    vector<int> jj, oo, ii;
    for (int i = 0; i < n; i++) {
        if(s[i] == 'J')
            jj.push_back(i);
        else if(s[i] == 'O')
            oo.push_back(i);
        else
            ii.push_back(i);
    }
    int ans = 1e9;
    for (int i = 0;i + k - 1 < (int)jj.size();i++) {
        auto u = upper_bound(oo.begin(), oo.end(), jj[i + k - 1]) - oo.begin();
        if(u + k - 1 >= (int)oo.size())
            continue;
        auto l = upper_bound(ii.begin(), ii.end(), oo[u + k - 1]) - ii.begin();
        if(l + k - 1 >= (int)ii.size())
            continue;
        int t = n - jj[i] - (n - 1 - ii[l + k - 1]);
        ans = min(ans, t - (3 * k));
    }
    if(ans == 1e9)
        ans = -1;
    cout << ans;
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...