Submission #548242

#	Time	Username	Problem	Language	Result	Execution time	Memory
548242		beaconmc	Bitaro the Brave (JOI19_ho_t1)	Pypy 3	50 / 100	661 ms	274432 KiB

joi2019_ho_t1

h,w = map(int, input().split())

grid = [list(input()) for i in range(h)]

prefx = [[0 for i in range(w)]for i in range(h)]
prefy = [[0 for i in range(w)]for i in range(h)]


for i in range(h):
    for j in range(w):
        if (j==0 and grid[i][j] == "O"):
            prefx[i][j] = 1
        else:
            prefx[i][j] = prefx[i][j-1] + bool(grid[i][j] == "O")

for i in range(h):
    for j in range(w):
        if (i==0 and grid[i][j] == "I"):
            prefy[i][j] = 1
        else:
            prefy[i][j] = prefy[i-1][j] + bool(grid[i][j] == "I")
ans = 0
for i in range(h):
    for j in range(w):
        if grid[i][j] == "J":
            ans += (prefx[i][w-1] - prefx[i][j])*(prefy[h-1][j] - prefy[i][j])
print(ans)
            

• Subtask 1: 20 / 20
• Subtask 2: 30 / 30
• Subtask 3: 0 / 50