제출 #1342617

#제출 시각아이디문제언어결과실행 시간메모리
1342617NipphitchJJOOII 2 (JOI20_ho_t2)C++20
100 / 100
9 ms3140 KiB
#include <bits/stdc++.h>
using namespace std;
const int N=2e5+5;

int n,m,ans=1e9;
char c[N];
deque <int> dq;
vector <pair <int,int>> vj,vo,vi;

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    for(int i=1;i<=n;i++) cin >> c[i];
    for(int i=1;i<=n;i++){
        if(c[i]=='J'){
            dq.push_back(i);
            if(dq.size()>m) dq.pop_front();
            if(dq.size()==m) vj.push_back({dq.front(),dq.back()});
        }
    }
    while(!dq.empty()) dq.pop_front();
    for(int i=1;i<=n;i++){
        if(c[i]=='O'){
            dq.push_back(i);
            if(dq.size()>m) dq.pop_front();
            if(dq.size()==m) vo.push_back({dq.front(),dq.back()});
        }
    }
    while(!dq.empty()) dq.pop_front();
    for(int i=1;i<=n;i++){
        if(c[i]=='I'){
            dq.push_back(i);
            if(dq.size()>m) dq.pop_front();
            if(dq.size()==m) vi.push_back({dq.front(),dq.back()});
        }
    }
    for(int i=0,j=0,k=0;i<vj.size() && j<vo.size() && k<vi.size();i++){
        while(j<vo.size() && vo[j].first<vj[i].second) j++;
        while(k<vi.size() && vi[k].first<vo[j].second) k++;
        if(i<vj.size() && j<vo.size() && k<vi.size()){
            //cout << vj[i].first << " -> " << vi[k].second << "\n";
            ans=min(ans,vi[k].second-vj[i].first+1-(m*3));
        }
    }
    cout << (ans==1e9?-1:ans);
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...