레이팅 미적용농부 존의 목초지는 정사각형 풀 "칸"들로 이루어진 \(N \times N\) 격자(\(1 \leq N \leq 500\))로 생각할 수 있다 (거대한 체스판을 떠올려 보자). 토양의 차이 때문에 어떤 칸의 풀은 다른 칸보다 더 푸르다. 각 칸 \((i,j)\)는 \(1 \ldots 200\) 범위의 정수 푸름 정도 \(G(i,j)\)로 표현된다.
농부 존은 목초지의 직사각형 부분 격자를 사진으로 찍고 싶어 한다. 그는 부분 격자가 충분히 푸르되 지나치게 푸르지는 않기를 바라기 때문에, \(G\)의 최솟값이 정확히 100인 부분 격자를 촬영하기로 했다. 그가 찍을 수 있는 서로 다른 사진이 몇 장인지 구하는 것을 도와주자. 부분 격자는 목초지 전체만큼 클 수도 있고 한 칸만큼 작을 수도 있다 (전체 부분 격자의 개수는 \(N^2(N+1)^2/4\)개이다 --- 이 수는 표준 32비트 정수에 담기에는 너무 클 수 있으므로, C++의 "long long" 같은 64비트 정수 자료형을 사용해야 할 수도 있다).
문제 제공: Brian Dean
채점 방식
- 테스트 케이스 1-5는 \(N\le 200\)을 만족한다.
- 테스트 케이스 6-10은 추가 제약이 없다.
문제 제공: Brian Dean
입력의 첫째 줄에 \(N\)이 주어진다. 다음 \(N\)개의 줄에는 각각 \(N\)개의 정수가 주어지며, 이들이 \(N \times N\) 목초지의 \(G(i,j)\) 값을 나타낸다.
농부 존이 찍을 수 있는 서로 다른 사진의 수, 즉 푸름 정도의 최솟값이 정확히 100인 직사각형 부분 격자의 개수를 출력한다.
이 문제에서 다루는 정수가 매우 클 수 있으므로 64비트 정수 자료형(예: C/C++의 "long long")이 필요할 수 있다.
3
57 120 87
200 100 150
2 141 1358riseoj 작성
출처 올림피아드 > USACO > 2020-2021 > February > Silver