Submission #1137668

#	Time	Username	Problem	Language	Result	Execution time	Memory
1137668		varun312	JJOOII 2 (JOI20_ho_t2)	C++20	100 / 100	12 ms	3032 KiB

ho_t2

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;

#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define endl "\n"
#define inf ((int)2e9)

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cout << fixed << setprecision(0);

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

    vector<int> J(n+1),O(n+1),I(n+1);
    for (int i = 1; i <= n; i++) {
        J[i] = J[i-1] + (s[i-1] == 'J');
        O[i] = O[i-1] + (s[i-1] == 'O');
        I[i] = I[i-1] + (s[i-1] == 'I');
    }

    // min cost to place K js, if first O is at I
    // vector<int> jc(n+1, inf);
    int ans = inf;
    for (int i = k+1; i <= n; i++) {
        if (J[i-1] < k || s[i-1] != 'O') {
            continue;
        }
        int ind = upper_bound(J.begin(), J.end(), J[i-1]-k) - J.begin();
        // cout << i << " " << ind << endl;
        int jc = (i - ind) - k;
        // cout << i << " " << jc[i] << endl;
        int indo = lower_bound(O.begin(), O.end(), O[i]+k-1) - O.begin();
        if (indo == n+1) {
            continue;
        }
        int oc = (indo - i + 1) - k;
        // cout << i << " " << indo << endl;
        if (I[n] - I[indo] < k) {
            continue;
        }
        int indi = lower_bound(I.begin(), I.end(), I[indo]+k) - I.begin();
        // cout << indo << " " << indi << endl;        
        int ic = (indi-indo) - k;
        ans = min(ans, jc + oc + ic);
    }

    cout << (ans == inf ? -1 : ans);
}

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