Submission #1024125

#	Time	Username	Problem	Language	Result	Execution time	Memory
1024125		Aurora	JJOOII 2 (JOI20_ho_t2)	C++14	0 / 100	0 ms	452 KiB

ho_t2

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

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

    ll n, k;
    cin >> n >> k;
    string s;
    cin >> s;

    // Находим первое вхождение 'J' с левой стороны
    ll l = -1;
    for (ll i = 0; i < n; ++i) {
        if (s[i] == 'J') {
            l = i;
            break;
        }
    }
    
    // Находим первое вхождение 'I' с правой стороны
    ll r = -1;
    for (ll i = n - 1; i >= 0; --i) {
        if (s[i] == 'I') {
            r = i;
            break;
        }
    }

    if (l == -1 || r == -1 || r - l + 1 < 3 * k) {
        cout << -1 << endl;
        return 0;
    }

    // Два указателя для нахождения минимальных операций 3
    ll min_ops = LLONG_MAX;
    vector<ll> cntJ(n + 1, 0), cntO(n + 1, 0), cntI(n + 1, 0);

    for (ll i = 0; i < n; ++i) {
        cntJ[i + 1] = cntJ[i] + (s[i] == 'J');
        cntO[i + 1] = cntO[i] + (s[i] == 'O');
        cntI[i + 1] = cntI[i] + (s[i] == 'I');
    }

    for (ll start = l; start <= r - 3 * k + 1; ++start) {
        ll end = start + 3 * k - 1;
        if (end > r) break;

        ll j_count = cntJ[start + k] - cntJ[start];
        ll o_count = cntO[start + 2 * k] - cntO[start + k];
        ll i_count = cntI[end + 1] - cntI[start + 2 * k];

        if (j_count == k && o_count == k && i_count == k) {
            min_ops = min(min_ops, cntO[end + 1] - cntO[start]);
        }
    }

    if (min_ops == LLONG_MAX) {
        cout << -1 << endl;
    } else {
        cout << min_ops - 3 * k << endl;
    }

    return 0;
}

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