1549번 - K

문제

s(i,k)를 배열 A의 i번째 원소부터 시작하는 연속된 k개 수의 합이라고 정의하자.

s(i,k) = A[i] + A[i+1] + ... + A[i+k-1]

i+k ≤ j일 때, s(i,k) 와 s(j,k)의 차이 (abs(s(i, k) - s(j, k)))를 최소로 하는 프로그램을 작성하시오. 즉, 동일한 길이의 겹치지 않는 두 부분 수열의 차이를 최소로 하는 것이다.

입력

첫째 줄에 n이 주어진다. n은 2보다 크거나 같고, 3,000보다 작거나 같은 자연수이다. 둘째 줄에는 배열 A의 원소가 A[0]부터 차례대로 주어진다. A[i] ≤ 1,000,000,000인 자연수 또는 0이다.

출력

첫째 줄에 값이 가장 작을 때 k를 출력하고, 둘째 줄에 차이의 최솟값을 출력한다. 만약 최솟값이 여러 개일 경우에는 k를 최대로 한다.

제한

힌트