OCR 문제를 자바로 풀었습니다.
종만북 알고리즘대로 구현하였고, 테스트 케이스도 잘 통과하여
문제가 없어보이는데, 자꾸 시간초과로 채점됩니다.
입력성능을 위해 BufferReader를 사용하여 배열 성분들을
각각 읽어들였는데, 무엇이 문제인가요??

문제링크 : https://www.algospot.com/judge/problem/read/OCR

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {

    static double[][] cache;
    static int m;
    static int q;
    static String words[];
    static double B[];
    static double T[][];
    static double M[][];
    static int[] S;
    static int[][] choice;
    static int n;

    public static void main(String[] args) throws Exception {
        // TODO Auto-generated method stub
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        m = Integer.parseInt(st.nextToken());
        q = Integer.parseInt(st.nextToken());
        words = new String[m+1];
        B = new double[m+1];
        T = new double[m+1][m+1];
        M = new double[m+1][m+1];
        int i = 1;
        st = new StringTokenizer(br.readLine(), " ");
        while (st.hasMoreTokens()) {
            words[i++] = st.nextToken();
        }
        i = 1;
        st = new StringTokenizer(br.readLine(), " ");
        while (st.hasMoreTokens()) {
            B[i++] = Math.log(Double.parseDouble(st.nextToken()));
        }
        for (int j = 0; j <= m; j++) {
            i = 1;
            if(j==0) {
                for(;i<=m;i++) {
                    T[j][i] = B[i];
                }
            }
            else {
                st = new StringTokenizer(br.readLine(), " ");
                while (st.hasMoreTokens()) {
                    T[j][i++] = Math.log(Double.parseDouble(st.nextToken()));
                }
            }
        }
        for (int j = 1; j <= m; j++) {
            i = 1;
            st = new StringTokenizer(br.readLine(), " ");
            while (st.hasMoreTokens()) {
                M[j][i++] = Math.log(Double.parseDouble(st.nextToken()));
            }
        }
        for (int j = 0; j < q; j++) {
            cache = new double[102][502];
            choice = new int[102][502];
            for (int a = 0; a < 102; a++) {
                for (int b = 0; b < 502; b++) {
                    cache[a][b] = 1;
                }
            }
            st = new StringTokenizer(br.readLine(), " ");
            n = Integer.parseInt(st.nextToken());
            S = new int[n];
            i = 0;
            while (st.hasMoreTokens()) {
                String s = st.nextToken();
                for (int t = 1; t <= m; t++) {
                    if (words[t].equals(s))
                        S[i++] = t;
                }
            }
            OCR(0, 0);
            bw.write(reconstruct(0, 0) + "\n");
            bw.flush();
        }
        bw.close();

    }

    static double OCR(int idx, int prev) {
        if (idx == n)
            return 0;
        double ret = -1e200;
        int wid = S[idx];
        if (cache[idx][prev] != 1) {
            return cache[idx][prev];
        }
        for (int i = 1; i <= m; i++) {
            double temp = T[prev][i] + M[i][wid] + OCR(idx + 1, i);
            if (temp > ret) {
                ret = temp;
                cache[idx][prev] = ret;
                choice[idx][prev] = i;
            }
        }
        return ret;

    }

    static String reconstruct(int idx, int prev) {
        int ch = choice[idx][prev];
        String ret = words[ch];
        if (idx < n - 1)
            ret = ret + " " + reconstruct(idx + 1, ch);
        return ret;
    }
}