Tontti

public class Tontti2 {
    public static void main(String[] args) {
        IO io = new IO();
        
        int n = io.nextInt();
        int m = io.nextInt();
        int x = io.nextInt();
        
        int[][] s = new int[n+1][m+1];
        
        for (int i=1; i<=n; i++) {
            String r = io.next();
            for (int j=1; j<=m; j++) {
                if (r.charAt(j-1) == '.') {
                    s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1];
                } else {
                    s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + 1;
                }
            }
        }
        
        int c = 0;
        int aMin = Math.max(0,(int)Math.ceil(Math.sqrt(x))-1);

        for (int i=1; i <= n-aMin; i++) {
            for (int j=1; j <= m-aMin; j++) {
                for (int a=aMin; a<=n-i && a<=m-j; a++) {
                    int tr = s[i+a][j+a] - s[i-1][j+a] - s[i+a][j-1] + s[i-1][j-1];
                    if (tr == x) {
                        c++;
                    } else if (tr > x) {
                        break;
                    }
                }
            }
        }
        
        io.println(c);
        
        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