Submission #1344013

#TimeUsernameProblemLanguageResultExecution timeMemory
1344013PakinDioxideJJOOII 2 (JOI20_ho_t2)C++17
100 / 100
10 ms2060 KiB
#include <bits/stdc++.h>
#define ll long long

using namespace std;

char C[3] = {'J', 'O', 'I'};

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int n, k; cin >> n >> k;
    map <char, vector <int>> P;
    string s; cin >> s;
    s = " " + s;
    for (int i = 1; i <= n; i++) P[s[i]].emplace_back(i);
    for (auto &e : C) if ((int) P[e].size() < k) { cout << -1 << '\n'; exit(0); }
    deque <int> dq;
    int mn = INT_MAX;
    for (auto &e : P['O']) {
        dq.emplace_back(e);
        if ((int) dq.size() > k) dq.pop_front();
        if ((int) dq.size() < k) continue;
        int L = dq.front(), R = dq.back();
        int it1 = upper_bound(P['J'].begin(), P['J'].end(), L) - P['J'].begin() - k;
        int it2 = upper_bound(P['I'].begin(), P['I'].end(), R) - P['I'].begin() + k - 1;
        if (it1 < 0 || it2 >= (int) P['I'].size()) continue;
        mn = min(mn, P['I'][it2] - P['J'][it1] + 1 - 3 * k);
    }
    cout << (mn == INT_MAX ? -1 : mn) << '\n';
}

#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...