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); // sums is offset by 1 remember.
            }
        }
 
        int waysOfChoosing = 0;
        
        for (int i = 0; i < height; i++) {
            for (int j = 0; j < width; j++) {
                int maxSidelength = Math.min(height - i, width - j);
                for (int sidelength = 1; sidelength <= maxSidelength; sidelength++) {
                    int treesInSquare = treesInSquare(sums, i, j, sidelength);
                    if (treesInSquare == idealAmountOfTrees) {
                        waysOfChoosing++;
                    }
                    if (treesInSquare > idealAmountOfTrees) {
                        break;
                    }
                }
            }
        }
     
 
        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: TIME LIMIT EXCEEDED

Test 14

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 15

Group: 3

Verdict: TIME LIMIT EXCEEDED