SRM623Div2Hard in Java

ApplesAndPears.java

import java.io.*;
import java.util.*;

public class ApplesAndPears {
    private int[][][] sb;
    
    public int getArea(String[] board, int K) {
	int N = board.length;
	sb = new int[3][N][N];

	for (int y=0; y<N; y++) {
	    for (int x=0; x<N; x++) {
		char c = board[y].charAt(x);
		if (c=='.') sb[0][y][x]=1;
		if (c=='A') sb[1][y][x]=1;
		if (c=='P') sb[2][y][x]=1;
		for (int i=0; i<3; i++) {
		    if (x>0) sb[i][y][x]+=sb[i][y][x-1];
		    if (y>0) sb[i][y][x]+=sb[i][y-1][x];
		    if (x>0 && y>0) sb[i][y][x]-=sb[i][y-1][x-1];
		}
	    }
	}

	int[] outer = new int[3];
	for (int i=0; i<3; i++) {
	    outer[i] = sb[i][N-1][N-1];
	}

	int ans=0;
	for (int x1=0; x1<N; x1++) {
	    for (int y1=0; y1<N; y1++) {
		for (int x2=x1; x2<N; x2++) {
		    for (int y2=y1; y2<N; y2++) {
			int r = (x2-x1+1)*(y2-y1+1);
			for (int i=0; i<3; i++) {
			    int a = sb[i][y2][x2];
			    if (x1>0) a-=sb[i][y2][x1-1];
			    if (y1>0) a-=sb[i][y1-1][x2];
			    if (x1>0 && y1>0) a+=sb[i][y1-1][x1-1];
			    int b = r-a;
			    if (b<=outer[i]-a && b<=K && ans<r) ans=r;
			    //System.out.println(""+x1+","+x2+","+y1+","+y2+","+r+","+a);
			}
		    }
		}
	    }
	}
	
	return ans;
    }

// CUT begin
	public static void main(String[] args){
		System.err.println("ApplesAndPears (1000 Points)");
		System.err.println();
		HashSet<Integer> cases = new HashSet<Integer>();
        for (int i = 0; i < args.length; ++i) cases.add(Integer.parseInt(args[i]));
        runTest(cases);
	}

	static void runTest(HashSet<Integer> caseSet) {
	    int cases = 0, passed = 0;
	    while (true) {
	    	String label = Reader.nextLine();
	    	if (label == null || !label.startsWith("--"))
	    		break;

            String[] board = new String[Integer.parseInt(Reader.nextLine())];
            for (int i = 0; i < board.length; ++i)
                board[i] = Reader.nextLine();
            int K = Integer.parseInt(Reader.nextLine());
            Reader.nextLine();
            int __answer = Integer.parseInt(Reader.nextLine());

            cases++;
            if (caseSet.size() > 0 && !caseSet.contains(cases - 1))
                continue;
    		System.err.print(String.format("  Testcase #%d ... ", cases - 1));

            if (doTest(board, K, __answer))
                passed++;
	    }
	    if (caseSet.size() > 0) cases = caseSet.size();
        System.err.println(String.format("%nPassed : %d/%d cases", passed, cases));

        int T = (int)(System.currentTimeMillis() / 1000) - 1401932913;
        double PT = T / 60.0, TT = 75.0;
        System.err.println(String.format("Time   : %d minutes %d secs%nScore  : %.2f points", T / 60, T % 60, 1000 * (0.3 + (0.7 * TT * TT) / (10.0 * PT * PT + TT * TT))));
	}

	static boolean doTest(String[] board, int K, int __expected) {
		for (int i = 0; i < board.length; i++) {
			board[i] = new String(board[i]);
		}
		long startTime = System.currentTimeMillis();
		Throwable exception = null;
		ApplesAndPears instance = new ApplesAndPears();
		int __result = 0;
		try {
			__result = instance.getArea(board, K);
		}
		catch (Throwable e) { exception = e; }
		double elapsed = (System.currentTimeMillis() - startTime) / 1000.0;

		if (exception != null) {
			System.err.println("RUNTIME ERROR!");
			exception.printStackTrace();
			return false;
		}
		else if (__result == __expected) {
			System.err.println("PASSED! " + String.format("(%.2f seconds)", elapsed));
			return true;
		}
		else {
			System.err.println("FAILED! " + String.format("(%.2f seconds)", elapsed));
			System.err.println("           Expected: " + __expected);
			System.err.println("           Received: " + __result);
			return false;
		}
	}

	static class Reader {
        private static final String dataFileName = "ApplesAndPears.sample";
	    private static BufferedReader reader;

	    public static String nextLine() {
	        try {
                if (reader == null) {
                    reader = new BufferedReader(new InputStreamReader(new FileInputStream(dataFileName)));
                }
                return reader.readLine();
	        }
	        catch (IOException e) {
	            System.err.println("FATAL!! IOException");
	            e.printStackTrace();
	            System.exit(1);
	        }
	        return "";
	    }
	}
// CUT end
}