ACM 2012 예선 문제 풀어보고 있는데 9006번 문제 풀다가 막혀서 질문드립니다.


제 풀이를 설명드리자면


1) 정답은 집과 집 사이가 아닌 어느 한 집일 것이다.

2) 그렇다면 모든 집에대해 그 집을 H로 두고 식을 계산해 최소값을 구한다.

3) O(1)만에 계산하는 방법으로는 각 그룹의 누적합과 역누적합을 이용해 상대적 위치를 이용해 갯수를 파악하고 찾아낸 공식을 이용해 구한다. (이부분이 설명드리기 까다롭네요..)


접근 방법자체가 틀린건지 계산하는 방식이 틀린건지 코딩이 틀린건지 왜 틀린건지................................ 도와주세요!!



https://gist.github.com/encia200/cf664906a011d21283624b54e14bdd69