시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB150685044.643%

문제

$N \times M$ 격자의 $(i, j)$ 칸에는 $1$ 이상 $9$ 이하의 숫자 $A_{i, j}$가 쓰여있다. 다음을 만족하는 $(x_1, x_2, y_1, y_2)$ 순서쌍의 개수를 세자.

  • $1 \leq x_1 < x_2 \leq N$, $1 \leq y_1 < y_2 \leq M$
  • $A_{x_1, y_1} + A_{x_1, y_2} + A_{x_2, y_1} + A_{x_2, y_2} = 20$

입력

첫 줄에는 $N$과 $M$이 공백으로 구분되어 주어진다.

이후 $N$개의 줄에 걸쳐 $A_{i, 1}, A_{i, 2}, \cdots, A_{i, M}$이 공백으로 구분되어 주어진다.

출력

위 조건을 만족하는 $(x_1, x_2, y_1, y_2)$의 개수를 출력하라.

제한

  • $2 \leq N, M \leq 10^5$
  • $NM \leq 10^5$
  • $1 \leq A_{i, j} \leq 9$

예제 입력 1

4 5
9 9 3 2 7
5 4 4 1 2
7 1 7 6 7
7 4 7 3 2

예제 출력 1

4
W3sicHJvYmxlbV9pZCI6IjM0MzE2IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVjMGFjXHVhYzAxXHVkNjE1IFx1YWMxY1x1YzIxOCBcdWMxMzhcdWFlMzAiLCJkZXNjcmlwdGlvbiI6IjxwPiROIFxcdGltZXMgTSQgXHVhY2E5XHVjNzkwXHVjNzU4ICQoaSwgaikkIFx1Y2U3OFx1YzVkMFx1YjI5NCAkMSQgXHVjNzc0XHVjMGMxICQ5JCBcdWM3NzRcdWQ1NThcdWM3NTggXHVjMjJiXHVjNzkwICRBX3tpLCBqfSRcdWFjMDAgXHVjNGYwXHVjNWVjXHVjNzg4XHViMmU0LiBcdWIyZTRcdWM3NGNcdWM3NDQgXHViOWNjXHVjODcxXHVkNTU4XHViMjk0ICQoeF8xLCB4XzIsIHlfMSwgeV8yKSQgXHVjMjFjXHVjMTFjXHVjMzBkXHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWMxMzhcdWM3OTAuPFwvcD5cclxuXHJcbjx1bD5cclxuPGxpPiQxIFxcbGVxIHhfMSAmbHQ7IHhfMiBcXGxlcSBOJCwgJDEgXFxsZXEgeV8xICZsdDsgeV8yIFxcbGVxIE0kPFwvbGk+XHJcbjxsaT4kQV97eF8xLCB5XzF9ICsgQV97eF8xLCB5XzJ9ICsgQV97eF8yLCB5XzF9ICsgQV97eF8yLCB5XzJ9ID0gMjAkPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYiBcdWM5MDRcdWM1ZDBcdWIyOTQgJE4kXHVhY2ZjICRNJFx1Yzc3NCBcdWFjZjVcdWJjMzFcdWM3M2NcdWI4NWMgXHVhZDZjXHViZDg0XHViNDE4XHVjNWI0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNzc0XHVkNmM0ICROJFx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDAgXHVhYzc4XHVjY2QwICRBX3tpLCAxfSwgQV97aSwgMn0sIFxcY2RvdHMsIEFfe2ksIE19JFx1Yzc3NCBcdWFjZjVcdWJjMzFcdWM3M2NcdWI4NWMgXHVhZDZjXHViZDg0XHViNDE4XHVjNWI0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWM3MDQgXHVjODcwXHVhYzc0XHVjNzQ0IFx1YjljY1x1Yzg3MVx1ZDU1OFx1YjI5NCAkKHhfMSwgeF8yLCB5XzEsIHlfMikkXHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NThcdWI3N2MuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIiwibGltaXQiOiI8dWw+XHJcbjxsaT4kMiBcXGxlcSBOLCBNIFxcbGVxIDEwXjUkPFwvbGk+XHJcbjxsaT4kTk0gXFxsZXEgMTBeNSQ8XC9saT5cclxuPGxpPiQxIFxcbGVxIEFfe2ksIGp9IFxcbGVxIDkkPFwvbGk+XHJcbjxcL3VsPlxyXG4ifSx7InByb2JsZW1faWQiOiIzNDMxNiIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkNvdW50aW5nIFJlY3RhbmdsZXMiLCJkZXNjcmlwdGlvbiI6IjxwPkluIGNlbGwgJChpLCBqKSQgb2YgYW4gJE4gXFx0aW1lcyBNJCBncmlkLCBhIG51bWJlciAkQV97aSwgan0kIGJldHdlZW4gJDEkIGFuZCAkOSQgKGluY2x1c2l2ZSkgaXMgd3JpdHRlbi4gQ291bnQgdGhlIG51bWJlciBvZiZuYnNwO3F1YWRydXBsZXMgJCh4XzEsIHhfMiwgeV8xLCB5XzIpJCB0aGF0IHNhdGlzZnkgdGhlIGZvbGxvd2luZy48XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT4kMSBcXGxlcSB4XzEgJmx0OyB4XzIgXFxsZXEgTiQsICQxIFxcbGVxIHlfMSAmbHQ7IHlfMiBcXGxlcSBNJDxcL2xpPlxyXG5cdDxsaT4kQV97eF8xLCB5XzF9ICsgQV97eF8xLCB5XzJ9ICsgQV97eF8yLCB5XzF9ICsgQV97eF8yLCB5XzJ9ID0gMjAkPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IHdpbGwgY29udGFpbiAkTiQgYW5kICRNJCwgc2VwYXJhdGVkIGJ5IHdoaXRlc3BhY2UuPFwvcD5cclxuXHJcbjxwPlRoZSAkaSQtdGggbGluZSBvZiB0aGUgdGhlIG5leHQgJE4kIGxpbmVzIHdpbGwgY29udGFpbiAkTSQgaW50ZWdlcnMsJm5ic3A7JEFfe2ksIDF9LCBBX3tpLCAyfSwgXFxjZG90cywgQV97aSwgTX0kLCBzZXBhcmF0ZWQgYnkgd2hpdGVzcGFjZS48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5PdXRwdXQgdGhlIG51bWJlciBvZiBxdWFkcnVwbGVzJm5ic3A7JCh4XzEsIHhfMiwgeV8xLCB5XzIpJCBzYXRpc2Z5aW5nIHRoZSBjb25kaXRpb25zIGluIHRoZSBwcm9ibGVtIHN0YXRlbWVudC4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIiwibGltaXQiOiI8dWw+XHJcblx0PGxpPiQyIFxcbGVxIE4sIE0gXFxsZXEgMTBeNSQ8XC9saT5cclxuXHQ8bGk+JE5NIFxcbGVxIDEwXjUkPFwvbGk+XHJcblx0PGxpPiQxIFxcbGVxIEFfe2ksIGp9IFxcbGVxIDkkPFwvbGk+XHJcbjxcL3VsPlxyXG4ifV0=

출처