Submission #1233251

#	Time	Username	Problem	Language	Result	Execution time	Memory
1233251		Muhammet	JJOOII 2 (JOI20_ho_t2)	C++20	100 / 100	9 ms	2732 KiB

ho_t2

#include "bits/stdc++.h"

using namespace std;

#define SZ(s) (int)s.size()

const int N = 2e5 + 5;

#define ll long long

int main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr);

    int n, k;
    string s;
    cin >> n >> k >> s;
    vector <vector <int>> v(3), a(3);
    for(int i = 0; i < n; i++) {
        if(s[i] == 'J') v[0].push_back(i);
        if(s[i] == 'O') v[1].push_back(i);
        if(s[i] == 'I') v[2].push_back(i);
    }

    for(int i = 0; i < 3; i++) {
        a[i].push_back(0);
        for(int j = 0; j < SZ(v[i])-1; j++) {
            a[i].push_back(a[i].back() + (v[i][j+1] - v[i][j] - 1));
        }
    }

    int ans = 1e9;
    for(int i = 0; i + k - 1 < SZ(v[0]); i++) {
        int s = a[0][i + k - 1] - a[0][i];
        int x = (v[0][i + k - 1] + 1);
        int t = lower_bound(v[1].begin(), v[1].end(), v[0][i + k - 1]) - v[1].begin();
        if(t + k - 1 >= SZ(v[1])) break;
        int y = (v[1][t]);
        s += (y - x);
        s += a[1][t + k - 1] - a[1][t];
        x = (v[1][t + k - 1] + 1);
        t = lower_bound(v[2].begin(), v[2].end(), v[1][t + k - 1]) - v[2].begin();
        if(t + k - 1 >= SZ(v[2])) break;
        y = (v[2][t]);
        s += (y - x);
        s += a[2][t + k - 1] - a[2][t];
        ans = min(ans, s);
    }

    cout << (ans == 1e9 ? -1 : ans);

    return 0;
}

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