Submission #1104275

#	Time	Username	Problem	Language	Result	Execution time	Memory
1104275		zephyrion	JJOOII 2 (JOI20_ho_t2)	C++17	0 / 100	1 ms	336 KiB

ho_t2

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

signed main() {
    int n, k;
    cin >> n >> k;
    string s1;
    cin >> s1;
    vector<int> prefix_j(n + 1, 0), prefix_o(n + 1, 0), prefix_i(n + 1, 0);

    for (int i = 0; i < n; i++) {
        prefix_j[i + 1] = prefix_j[i] + (s1[i] == 'J');
        prefix_o[i + 1] = prefix_o[i] + (s1[i] == 'O');
        prefix_i[i + 1] = prefix_i[i] + (s1[i] == 'I');
    }

    int ans = INT_MAX;

    for (int i = 0; i <= n - 3 * k; i++) {
        if (s1[i] != 'J') continue;

        bool valid = true;

        if ((prefix_o[i + k] - prefix_o[i]) < k || (prefix_i[i + 2 * k] - prefix_i[i + k]) < k) {
            valid = false;
        }

        if (!valid) continue;

        int tmp = 0;

        tmp += k - (prefix_j[i + k] - prefix_j[i]);
        
        int o_start = i + k;
        int o_end = o_start + k - 1;
        tmp += k - (prefix_o[o_end + 1] - prefix_o[o_start]);

        int i_start = o_end + 1;
        int i_end = i_start + k - 1;
        tmp += k - (prefix_i[i_end + 1] - prefix_i[i_start]);

        ans = min(ans, tmp);
    }

    if (ans == INT_MAX){
        cout << -1;
    }
    else{
        cout << ans;
    }
}

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