컴백
시간 제한1초메모리 제한512 MB
배열을 왼쪽으로 한 칸씩 회전시키면서 각 단계마다 합이 X 이하인 모든 연속 부분수열의 개수와 그 합들의 총합을 구한다.
문제
안토니오는 공공 정원에 다녀온 뒤 집으로 돌아와서, 음이 아닌 정수 n개로 이루어진 배열과 수 X를 발견한다. 심심해진 그는 이 배열로 n단계에 걸친 게임을 만들기로 한다. 각 단계에서 안토니오는 두 가지 행동을 한다.
- 합이 X 이하인 배열의 모든 부분수열을 찾아, 그러한 부분수열들의 합의 총합과 그 개수를 기억한다.
- 배열을 왼쪽으로 한 칸 원형 이동한다.
각 단계에서 안토니오가 기억하는 값을 구하라.
입력
첫째 줄에 n과 X가 주어진다.
둘째 줄에 배열의 원소 n개가 공백으로 구분되어 주어진다.
출력
n개의 줄을 출력한다.
i번째 줄에는 i단계에서 유효한 부분수열들의 합의 총합과 그 개수를 공백으로 구분하여 출력한다.
제한
- n ≤ 100,000, X ≤ 1,000,000,000
- 배열의 원소는 0과 10^6 사이이다.
- 주어진 배열의 부분수열은 연속한 위치에 있는 원소들로 이루어진다.
힌트
- 1단계. 유효한 부분수열들의 합의 총합: 1 + 2 + 3 + (1 + 2) + (2 + 3) = 14. 유효한 부분수열은 5개이다. 배열은 2, 3, 1이 된다.
- 2단계. 유효한 부분수열들의 합의 총합: 2 + 3 + 1 + (2 + 3) + (3 + 1) = 15. 유효한 부분수열은 5개이다. 배열은 3, 1, 2가 된다.
- 3단계. 유효한 부분수열들의 합의 총합: 3 + 1 + 2 + (3 + 1) + (1 + 2) = 13. 유효한 부분수열은 5개이다. 배열은 1, 2, 3이 된다.