Submission #1125569

#TimeUsernameProblemLanguageResultExecution timeMemory
1125569secretwood01JJOOII 2 (JOI20_ho_t2)Java
100 / 100
153 ms23100 KiB
import java.util.*;
import java.io.*;

public class ho_t2 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter pw = new PrintWriter(System.out);
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());
        int [] jp = new int[N+1];
        int [] op = new int[N+1];
        int [] ip = new int[N+1];
        ArrayList<Integer> j = new ArrayList<Integer>();
        ArrayList<Integer> o = new ArrayList<Integer>();
        ArrayList<Integer> i = new ArrayList<Integer>();
        st = new StringTokenizer(br.readLine());
        String S = st.nextToken();
        jp[0] = 0;op[0] = 0;ip[0] = 0;
        for (int k=0;k<N;k++) {
            jp[k+1] = jp[k];
            op[k+1] = op[k];
            ip[k+1] = ip[k];
            char c = S.charAt(k);
            if (c=='J') {
                jp[k+1]++;
                j.add(k);
            } else if (c=='O') {
                op[k+1]++;
                o.add(k);
            } else {
                ip[k+1]++;
                i.add(k);
            }
        }
        int ans = Integer.MAX_VALUE;
        if (j.size()>=K) {
            int jend = K-1;
            int oend = 0;
            int iend = 0;
            while (jend<j.size()) {
                while (oend<o.size() && op[o.get(oend)+1]-op[j.get(jend)]<K) oend++;
                if (oend>=o.size()) break;
                while (iend<i.size() && ip[i.get(iend)+1]-ip[o.get(oend)]<K) iend++;
                if (iend>=i.size()) break;
                ans = Math.min(ans, i.get(iend)-j.get(jend-K+1)+1-3*K);
                jend++;
            }
        }
        if (ans==Integer.MAX_VALUE) ans = -1;
        pw.println(ans);
        pw.close();
        br.close();
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...