시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 512 MB | 166 | 107 | 100 | 64.516% |
Bitaro the Brave faces the Devil.
Bitaro is going to attack the Devil by arranging jewels, orbs and ingots on an H times W grid and casting a spell. The square at the i-th row (1 ≤ i ≤ H) from the top and the j-th column (1 ≤ j ≤ W) from the left is denoted by (i, j).
Now, Bitaro has arranged one of these three types on each square. Bitaro is going to cast a spell, the power of which is determined by the arrangement of jewels, orbs and ingots. Specifically, the power equals to the number of quadruplets of integers (i, j, k, ℓ) (1 ≤ i < k ≤ H, 1 ≤ j < ℓ ≤ W) satisfying the following condition.
Condition: Bitaro has arranged a jewel on the square (i, j), an orb on the square (i, ℓ) and an ingot on the square (k, j).
Bitaro is wondering the power of the spell.
Write a program which, given the arrangement of jewels, orbs and ingots, calculates the power of the spell Bitaro casts.
Read the following data from the standard input.
H W S1 : SH
Si (1 ≤ i ≤ H) is a string of length W. The item arranged on the square (i, j) (1 ≤ j ≤ W) is a jewel if the j-th character of Si is J
, an orb if it is O
and an ingot if it is I
.
Write one line to the standard output. The output should contain the power of the spell Bitaro casts.
J
, O
, or I
(1 ≤ i ≤ H).번호 | 배점 | 제한 |
---|---|---|
1 | 20 | H ≤ 100, W ≤ 100. |
2 | 30 | H ≤ 500, W ≤ 500. |
3 | 50 | No additional constraints. |
3 4 JOIJ JIOO IIII
3
In this sample, 3 quadruplets (i, j, k, ℓ) = (1, 1, 3, 2), (2, 1, 3, 3), (2, 1, 3, 4) satisfy the condition, so you should output 3.
4 4 JJOO JJOO IIJO IIIJ
17