#agc028f2. [agc028_f2]Reachable Cells
[agc028_f2]Reachable Cells
Problem Statement
Problem F and F2 are the same problem, but with different constraints and time limits.
We have a board divided into horizontal rows and vertical columns of square cells. The cell at the -th row from the top and the -th column from the left is called Cell . Each cell is either empty or occupied by an obstacle. Also, each empty cell has a digit written on it. If 1
, 2
, ..., or 9
, Cell is empty and the digit is written on it. If #
, Cell is occupied by an obstacle.
Cell is reachable from cell when the following conditions are all met:
- Cells and are different.
- Cells and are both empty.
- One can reach from Cell to Cell by repeatedly moving right or down to an adjacent empty cell.
Consider all pairs of cells such that cell is reachable from cell . Find the sum of the products of the digits written on cell and cell for all of those pairs.
Constraints
- is one of the following characters:
1
,2
, ...9
and#
.
Input
Input is given from Standard Input in the following format:
Output
Print the sum of the products of the digits written on cell and cell for all pairs such that cell is reachable from cell .
Sample Input 1
Sample Output 1
There are five pairs of cells such that cell is reachable from cell , as follows:
- ,
- ,
- ,
- ,
- ,
The product of the digits written on cell and cell is for all of those pairs, so the answer is .