Tontti

#!/usr/bin/env python3

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

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

def viistorivin_osumat(x, y, p, kum_riv, kum_sar):
    '''palauta sopivien (p puuta) neliötonttien määrä viistorivillä'''
    maara = 0
    y_max = len(kum_riv) - 1
    x_max = len(kum_riv[0]) - 1
    vika_x = x + min(x_max - x, y_max - y)
    x2 = x
    y2 = y
    puita_nyt = kum_riv[y][x] - kum_riv[y][x - 1]
    while x2 <= vika_x:
        if puita_nyt <= p:
            if puita_nyt == p:
                maara += 1
            # venytetään tonttia oikeasta alakulmasta
            x2 += 1
            if x2 > vika_x:
                break
            y2 += 1
            # oikea pystysivu lisää, ilman alakulmaa
            puita_nyt += kum_sar[y2 - 1][x2] - kum_sar[y - 1][x2]
            # alasivu lisää, oikean alakulman kanssa
            puita_nyt += kum_riv[y2][x2] - kum_sar[y2][x - 1]
        else:
            # siirretään aloituskohtaa yhdellä eteenpäin, alaviistoon
            x += 1
            y += 1
            x2 = x
            y2 = y
            puita_nyt = kum_riv[y][x] - kum_riv[y][x - 1]
    return maara

def sopivia_tontteja(p, kum_riv, kum_sar):
    y_max = len(kum_riv) - 1
    x_max = len(kum_riv[0]) - 1
    maara = 0
    for x in range(1, x_max + 1):
        maara += viistorivin_osumat(x, 1, p, kum_riv, kum_sar)
    for y in range(2, y_max + 1):
        maara += viistorivin_osumat(1, y, p, 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 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():
    n, m, k = map(int, input().split())
    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: WRONG ANSWER

Test 2

Subtask: 1

Verdict: WRONG ANSWER

Test 3

Subtask: 1

Verdict: WRONG ANSWER

Test 4

Subtask: 1

Verdict: WRONG ANSWER

Test 5

Subtask: 1

Verdict: WRONG ANSWER

Test 6

Subtask: 2

Verdict: TIME LIMIT EXCEEDED

Test 7

Subtask: 2

Verdict: TIME LIMIT EXCEEDED

Test 8

Subtask: 2

Verdict: TIME LIMIT EXCEEDED

Test 9

Subtask: 2

Verdict: TIME LIMIT EXCEEDED

Test 10

Subtask: 2

Verdict: TIME LIMIT EXCEEDED

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