Submission #753825

#	Time	Username	Problem	Language	Result	Execution time	Memory
753825		vjudge1	JJOOII 2 (JOI20_ho_t2)	C++17	0 / 100	1 ms	316 KiB

ho_t2

#include <bits/stdc++.h>
 
#define int long long
#define ff first
#define ss second
#define pb push_back

using namespace std;

const int N = 2e5+10;
const int INF = 1e18;

int suffo[N];
int suffi[N];
int n,k;
string s;
int cnt;

void solve(){ 
    cin>>n>>k;
    string b;
    cin>>b;
    s = "0"+b;
    if(s[n] == 'O') suffo[n] = 1;
    else suffo[n] = 0;
    if(s[n] == 'I') suffi[n] = 1;
    else suffi[n] = 0;
    for(int i = n-1;i>0;i--){
        if(s[i] == 'O') suffo[i] = suffo[i+1]+1;
        else suffo[i] = suffo[i+1];
        if(s[i] == 'I') suffi[i] = suffi[i+1]+1;
        else suffi[i] = suffi[i+1];
    }
    int pos = -1;
    int pos2 = -1;
    for(int i = 1;i<=n;i++){
        if(s[i] == 'J') cnt++;
        if(cnt>=k && suffo[i]>=k && suffi[i]>=k){
            pos = i;
        }
    }
    if(pos == -1){
        cout<<-1;
        return;
    }
    int pos1 = -1;
    cnt = 0;
    for(int i = n;i>0;i--){
        if(suffi[i] != 0){
            pos1 = i; break;
        }
    } 
    for(int i = pos1;i>0;i--){
        if(s[i] == 'J') cnt++;
        if(cnt == k){
            pos2 = i;
            break;
        }
    }
    cout<<(pos1-pos2+1)-k*3;
}
signed main(){
    // freopen("herding.in","r",stdin);  
    // freopen("herding.out","w",stdout);
    int t = 1;
    // cin>>t;   
    for(int i = 1;i<=t;i++){
        // cout<<"Case "<<i<<":\n";
        solve();
    }
}

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