중앙값
시간 제한1초메모리 제한128 MB
N개의 온도 측정값에서 길이 K인 모든 연속 구간의 중앙값을 구해 그 합을 계산하는 문제입니다.
문제
중앙값은 수열을 오름차순으로 정렬했을 때 왼쪽에서 (길이 + 1) / 2번째에 있는 값이다. 이 위치는 정수 나눗셈으로 계산한다. 길이가 6이면 3번째 값, 길이가 5이면 3번째 값이 중앙값이다.
1초에 한 번씩 측정한 온도 기록이 N개 주어진다. 측정이 K번 이상 이루어진 뒤에는 매초마다 최근 K초 동안의 온도 K개를 정렬했을 때의 중앙값이 표시된다.
길이가 N인 수열에서 길이 K인 모든 연속 부분 수열의 중앙값을 구하고, 그 중앙값들의 합을 출력하라.
입력
첫째 줄에 두 정수 N과 K가 주어진다. N은 250,000 이하의 자연수이고, K는 5,000 이하의 자연수이며, 항상 K ≤ N이다.
둘째 줄부터 N개의 줄에 온도 값이 하나씩 주어진다. 각 값은 0 이상 65,536 이하의 정수이다.
출력
길이 K인 모든 연속 부분 수열의 중앙값의 합을 첫째 줄에 출력한다. 정답은 2^63 - 1 이하이다.