제출 #1343245

#제출 시각아이디문제언어결과실행 시간메모리
1343245coin_JJOOII 2 (JOI20_ho_t2)C++20
0 / 100
1 ms344 KiB
#include <bits/stdc++.h>
#define int long long
using namespace std;

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(nullptr);
    int n, k;
    cin >> n >> k;
    string s;
    cin >> s;
    vector<int> prefJ(n, 0), prefO(n, 0), prefI(n, 0);
    vector<int> nxtJ(n, -1), nxtO(n, -1), nxtI(n, -1);
    int lastJ = -1, lastO = -1, lastI = -1;
    for (int i = 0; i < n; i++){
        if (s[i] == 'J'){
            prefJ[i]++;
            if (lastJ != -1){
                nxtJ[lastJ] = i;
            }
            lastJ = i;
        }
        if (s[i] == 'O'){
            prefO[i]++;
            if (lastO != -1){
                nxtO[lastO] = i;
            }
            lastO = i;
        }
        if (s[i] == 'I'){
            prefI[i]++;
            if (lastI != -1){
                nxtI[lastI] = i;
            }
            lastI = i;
        }
    }
    for (int i = 1; i < n; i++){
        prefJ[i] += prefJ[i-1];
        prefO[i] += prefO[i-1];
        prefI[i] += prefI[i-1];
    }
    // fix l, for once to get is
    // if push l up 1, then furthest j drops and jumps to the closest one, same with o
    // solve for l = 0 first
    int firstJ = -1, firstO = -1, firstI = -1;
    int farJ = 0, farO = 0, farI = 0;
    int curJ = 0, curO = 0, curI = 0;
    for (int i = 0; i < n; i++){
        if (s[i] == 'J' && curJ < k){
            if (firstJ == -1){
                firstJ = i;
            }
            curJ++;
            farJ = i;
        }
        if (s[i] == 'O' && curO < k && curJ == k){
            if (firstO == -1){
                firstO = i;
            }
            curO++;
            farO = i;
        }
        if (s[i] == 'I' && curI < k && curO == k){
            if (firstI == -1){
                firstI = i;
            }
            curI++;
            farI = i;
        }
    }
    if (curI < k){
        cout << -1;
        return 0;
    }
    int ans = farI - firstJ + 1 - 3*k;
    while(nxtJ[farJ] != -1){
        int newFarJ = nxtJ[farJ];
        int newFirstJ = nxtJ[firstJ];
        int numO = prefO[newFarJ] - (farJ == 0 ? 0 : prefO[farJ-1]);
        int newFarO = farO;
        int newFirstO = firstO;
        while(numO > 0 && nxtO[newFarO] != -1){
            newFarO = nxtO[newFarO];
            newFirstO = nxtO[newFirstO];
            numO--;
        }
        if (numO > 0) break;
        int numI = prefI[newFarO] - (farO == 0 ? 0 : prefO[farO-1]);
        int newFarI = farI;
        int newFirstI = firstI;
        while(numI > 0 && nxtI[newFarI] != -1){
            newFarI = nxtI[newFarI];
            newFirstI = nxtI[newFirstI];
        }
        if (numI > 0) break;
        firstJ = newFirstJ, firstO = newFirstO, firstI = newFirstI;
        farJ = newFarJ, farO = newFarO, farI = newFarI;
        ans = min(ans, farI - firstJ + 1 - 3*k);
    }
    cout << ans;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...