Submission #1118619

#	Time	Username	Problem	Language	Result	Execution time	Memory
1118619		secretwood01	JJOOII 2 (JOI20_ho_t2)	Java	0 / 100	66 ms	8932 KiB

ho_t2

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());
        TreeSet<Integer> Js, Is;
        Js = new TreeSet<Integer>();Is = new TreeSet<Integer>();
        int [] O = new int [N];
        int [] J = new int [N];
        st = new StringTokenizer(br.readLine());
        String S = st.nextToken();
        O[0] = 0;J[0] = 0;
        for (int i=0;i<N;i++) {
            char c = S.charAt(i);
            if (i!=0) {
                O[i]=O[i-1];
                J[i]=J[i-1];
            }
            if (c=='J') {
                Js.add(i);
                J[i]++;
            }
            else if (c=='I') Is.add(i);
            else O[i]++;
        }
        int ans = Integer.MAX_VALUE;
        int left = Js.pollFirst();
        int right = next(Is, K, left);
        while (right>0) {
            int numOs = O[right] - O[left];
            int numJs = J[right] - J[left]+1;;
            if (numOs<K || numJs<K) {
                right = next(Is, K, right);
            } else {
                ans = Math.min(ans, right-left+1-(3*K));
                left = Js.pollFirst();
                right = next(Is, K, left);
            }
        }
        if (ans==Integer.MAX_VALUE) ans = -1;
        pw.println(ans);
        pw.close();
        br.close();
    }
    public static int next(TreeSet<Integer> s, int n, int curr) {
        int counter = n;
        int toReturn = curr;
        while (counter>0 && s.higher(toReturn)!=null) {
            toReturn = s.higher(toReturn);
            counter--; 
        }
        if (counter>0) return -1;
        return toReturn;
    }
}

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