Submission #1180344

#	Time	Username	Problem	Language	Result	Execution time	Memory
1180344		nekolie	JJOOII 2 (JOI20_ho_t2)	C++20	100 / 100	19 ms	1804 KiB

ho_t2

#include <bits/stdc++.h>
using namespace std;

int n,k; string s;
int jump(int i, vector<int> &v) {
    if (i == -1 || v.empty() || v.back() < i)
        return -1;
    int j = (lower_bound(v.begin(),v.end(),i)-v.begin());
    if (j+k-1 >= v.size())
        return -1;
    return v[j+k-1];
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> n >> k >> s;
    vector<int> indj, indo, indi;
    for (int i = 0; i < n; i++) {
        if (s[i] == 'J')
            indj.push_back(i);
        else if (s[i] == 'O')
            indo.push_back(i);
        else
            indi.push_back(i);
    }
    int odp = 1000000000;
    for (int i = 0; i < n; i++) {
        int j = jump(jump(jump(i,indj),indo),indi);
        if (j != -1)
            odp = min(odp,j-i-3*k+1);
    }
    cout << ((odp == 1000000000) ? -1 : odp) << endl;
    return 0;
}

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