Tontti

#!/usr/bin/env python
# -*- coding: utf-8 -*-

# miten monella n x m -ruudukon k x k -neliötontilla on p puuta?

# esimerkkisyöte:
'''
4 6 3
..**..
**....
*...*.
..*...
'''

n, m, k = map(int, raw_input().split())

def laske(x, y, x2, y2, p, laskettavat, kr, ks):
    '''laske pisteestä (x, y) alas ja oikealle sijoittuvat sopivat tontit'''
    maara = 0
    haara_x2 = None
    tasa_nahty = False

    while p <= k:
        if p < k:
            haara_x2 = x2
            haara_y2 = y2
            haara_p = p
        elif p == k:
            maara += 1
            if not tasa_nahty:
                haara_x2 = x2
                haara_y2 = y2
                haara_p = p
                tasa_nahty = True

        if x2 == m or y2 == n:
            break

        x2 += 1
        y2 += 1
        # lisää oikea reuna, myös alakulma
        p += ks[y2][x2] - ks[y - 1][x2]
        # lisää alareuna, ei alakulmaa
        p += kr[y2][x2 - 1] - kr[y2][x - 1]

    if haara_x2:
        if x == haara_x2:
            # 1x1 tontti
            if y == 1 and x < m:
                # haaraudu oikealle (vain ylärivistä)
                haara_x2 = x + 1
                p_oik = kr[y][haara_x2] - kr[y][haara_x2 - 1]
                laskettavat.append((haara_x2, y, haara_x2, y, p_oik))
            # haaraudu alas
            if y < n:
                haara_y2 = y + 1
                p_alas = ks[haara_y2][x] - ks[haara_y2 - 1][x]
                laskettavat.append((x, haara_y2, x, haara_y2, p_alas))
        else:
            if y == 1:
                # haaraudu oikealle (vain ylärivistä)
                # leikkaa puumäärästä vasen ja alarivi pois
                p_oik = haara_p - ks[haara_y2][x]
                p_oik -= kr[haara_y2][haara_x2] - kr[haara_y2][x] # ei vas. alakulmaa
                laskettavat.append((x + 1, y, haara_x2, haara_y2 - 1, p_oik))
            # haaraudu alas
            # leikkaa puumäärästä oikea ja ylärivi pois
            p_alas = haara_p - (ks[haara_y2][haara_x2] - ks[y][haara_x2]) # ei oik. yläkulmaa
            p_alas -= kr[y][haara_x2] - kr[y][x - 1]
            laskettavat.append((x, y + 1, haara_x2 - 1, haara_y2, p_alas))

    return maara

def sopivia_tontteja(p, kum_riv, kum_sar):
    maara = 0
    laskettavat = [(1, 1, 1, 1, kum_riv[1][1])]
    while laskettavat:
        x1, y1, x2, y2, p = laskettavat.pop()
        maara += laske(x1, y1, x2, y2, p, laskettavat, kum_riv, kum_sar)
    return maara

def lue_ruudukko(n, m):
    kum_riv = [[0] * (m + 1)]
    kum_sar = [[0] * (m + 1)]
    for y in range(n):
        rivi = [1 if c == '*' else 0 for c in raw_input().rstrip()]
        kr = [0]
        ks = [0]
        for x, v in enumerate(rivi):
            kr.append(kr[-1] + v)
            ks.append(kum_sar[-1][x + 1] + v)
        kum_riv.append(kr)
        kum_sar.append(ks)
    return kum_riv, kum_sar

def main():
    kum_rivit, kum_sarakkeet = lue_ruudukko(n, m)
    print(sopivia_tontteja(k, kum_rivit, kum_sarakkeet))

if __name__ == '__main__':
    main()

Test 1

Subtask: 1

Verdict: ACCEPTED

Test 2

Subtask: 1

Verdict: ACCEPTED

Test 3

Subtask: 1

Verdict: ACCEPTED

Test 4

Subtask: 1

Verdict: ACCEPTED

Test 5

Subtask: 1

Verdict: ACCEPTED

Test 6

Subtask: 2

Verdict: TIME LIMIT EXCEEDED

Test 7

Subtask: 2

Verdict: TIME LIMIT EXCEEDED

Test 8

Subtask: 2

Verdict: ACCEPTED

Test 9

Subtask: 2

Verdict: ACCEPTED

Test 10

Subtask: 2

Verdict: ACCEPTED

Test 11

Subtask: 3

Verdict: TIME LIMIT EXCEEDED

Test 12

Subtask: 3

Verdict: TIME LIMIT EXCEEDED

Test 13

Subtask: 3

Verdict: TIME LIMIT EXCEEDED

Test 14

Subtask: 3

Verdict: TIME LIMIT EXCEEDED

Test 15

Subtask: 3

Verdict: TIME LIMIT EXCEEDED