PythonでJOI難易度5を埋める #13

A - 勇者ビ太郎 (Bitaro the Brave)

考えたこと
前から愚直に累積和をすると，PythonはTLE，PyPyだとMLEになります．
そこで後ろから，調べることにします．Oは後ろから調べると行ごとに値を保持すればいいので，大きいlistを使う必要がありません．Iは列の数だけlistを作って保持します．

h, w = map(int, input().split())
s = [input() for _ in range(h)]

cnt_i = [0] * w
ans = 0

for i in reversed(range(h)):
    cnt_o = 0
    for j in reversed(range(w)):
        if s[i][j] == 'J':
            ans += cnt_i[j] * cnt_o
        if s[i][j] == 'O':
            cnt_o += 1
        if s[i][j] == 'I':
            cnt_i[j] += 1

print(ans)

ありがとうございます．