Tontti

public class TonttiTehtava {
 
    private static int treesInSquare(int[][] sums, int i, int j, int sidelength) {
        return sums[i + sidelength][j + sidelength]
                - sums[i + sidelength][j]
                - sums[i][j + sidelength]
                + sums[i][j];
    }
 
    public static void main(String[] args) {
 
        IO io = new IO();
        int height = io.nextInt();
        int width = io.nextInt();
        int idealAmountOfTrees = io.nextInt();
 
        String[] rows = new String[height];
        for (int i = 0; i < height; i++) {
            rows[i] = io.next();
        }
 
        int[][] sums = new int[height + 1][width + 1];
 
        for (int i = 0; i <= height; i++) {
            sums[i][0] = 0;
        }
 
        for (int j = 1; j <= width; j++) {
            sums[0][j] = 0;
        }
 
        for (int i = 1; i <= height; i++) {
            for (int j = 1; j <= width; j++) {
                sums[i][j] = sums[i - 1][j] - sums[i - 1][j - 1] + sums[i][j - 1]
                        + (rows[i - 1].charAt(j - 1) == '*' ? 1 : 0); 
            }
        }
 
        int waysOfChoosing = 0;
 
        for (int i = 0; i < height; i++) {
            for (int j = 0; j < width; j++) {
                int minSidelength = 1;
                int maxSidelength = Math.min(height - i, width - j);
                while (minSidelength <= maxSidelength) {
                    int midpoint = (minSidelength + maxSidelength) >>> 1;
                    int treesInSquare = treesInSquare(sums, i, j, midpoint);
                    if (treesInSquare == idealAmountOfTrees) {
                        waysOfChoosing++;
                        int length1 = midpoint - 1;
                        while (length1 >= minSidelength && treesInSquare(sums, i, j, length1) == idealAmountOfTrees) {
                            waysOfChoosing++;
                            length1--;
                        }
                        int length2 = midpoint + 1;
                        while (length2 <= maxSidelength && treesInSquare(sums, i, j, length2) == idealAmountOfTrees) {
                            waysOfChoosing++;
                            length2++;
                        }
                        break;
                    } else if (treesInSquare < idealAmountOfTrees) {
                        minSidelength = midpoint + 1;
                    } else if (treesInSquare > idealAmountOfTrees) {
                        maxSidelength = midpoint - 1;
                    }
                }
            }
        }
 
        io.println(waysOfChoosing);
        io.close();
    }
}

Test 1

Group: 1

Verdict: ACCEPTED

Test 2

Group: 1

Verdict: ACCEPTED

Test 3

Group: 1

Verdict: ACCEPTED

Test 4

Group: 1

Verdict: ACCEPTED

Test 5

Group: 1

Verdict: ACCEPTED

Test 6

Group: 2

Verdict: ACCEPTED

Test 7

Group: 2

Verdict: ACCEPTED

Test 8

Group: 2

Verdict: ACCEPTED

Test 9

Group: 2

Verdict: ACCEPTED

Test 10

Group: 2

Verdict: ACCEPTED

Test 11

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 12

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 13

Group: 3

Verdict: ACCEPTED

Test 14

Group: 3

Verdict: ACCEPTED

Test 15

Group: 3

Verdict: ACCEPTED