제출 #1158965

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1158965		rbt729	JJOOII 2 (JOI20_ho_t2)	C++20	100 / 100	14 ms	3000 KiB

ho_t2

#include <iostream>
#include <algorithm>
#include <vector>
#include <numeric>
#include <string>

using namespace std;

int main() {
    int n, k, ans = 1e8;
    vector<int> pj, po, pi;
    string s;
    cin >> n >> k >> s;
    pj.push_back(0);
    po.push_back(0);
    pi.push_back(0);
    for(int i = 0; i < n; i++){
        pj.push_back(pj[i] + (s[i] == 'J'));
        po.push_back(po[i] + (s[i] == 'O'));
        pi.push_back(pi[i] + (s[i] == 'I'));
    }
    for(int i = 0; i < n; i++){
        if(s[i] == 'J'){
            int l = i, r = n-1, target = pj[i+1] + k-1, curSum = 0, a = 0;
            if(target > pj[n]){
                break;
            }
            //cout << target << endl;
            while(l <= r){
                int mid = (l+r)/2;
                if(pj[mid+1] < target){
                    l = mid+1;
                }
                else{
                    r = mid-1;
                    a = mid;
                }
                //cout << l << " " << r << endl;
            }
            //cout << a << " ";
            int pos = a;
            l = a;
            r = n-1;
            target = po[l+1] + k;
            if(target > po[n]){
                break;
            }
            //cout << target << endl;
            while(l <= r){
                int mid = (l+r)/2;
                if(po[mid+1] < target){
                    l = mid+1;
                }
                else{
                    r = mid-1;
                    a = mid;
                }
                //cout << l << " " << r << endl;
            }
            //cout << a << " ";
            pos = a;
            l = a;
            r = n-1;
            target = pi[l+1] + k;
            if(target > pi[n]){
                break;
            }
            //cout << target;
            while(l <= r){
                int mid = (l+r)/2;
                if(pi[mid+1] < target){
                    l = mid+1;
                }
                else{
                    r = mid-1;
                    a = mid;
                }
                //cout << l << " " << r << endl;
            }
            //cout << a << endl;
            curSum += ((a-i+1) - 3*k);
            ans = min(ans, curSum);
        }
    }
    if(ans == 1e8){
        cout << -1;
    }
    else{
        cout << ans;
    }
}

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