시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 512 MB 4 4 4 100.000%

문제

길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. 

  • l r k: 부분수열 Al, Al+1, ..., AR 에 대해, 해당 부분 수열에서 k개의 부분 수열을 골라서 부분 수열의 원소의 합의 최댓값을 출력하라. 고른 부분 수열은 각각 비어있지 않아야 하며, 서로 겹쳐서는 안된다.

입력

첫째 줄에 수열의 크기 N, 쿼리의 개수 M이 주어진다. (1 ≤ N, M ≤ 35,000)

둘째 줄에는 A1, A2, ..., AN이 주어진다. (-35,000 ≤ Ai < 35,000)

셋째 줄부터 M개의 줄에는 쿼리가 한 줄에 하나씩 주어진다. (1 ≤ l ≤ r ≤ N, 1 ≤ k ≤ r - l + 1)

출력

쿼리의 결과를 한 줄에 하나씩 출력한다.

예제 입력 1

5 5
-1 2 -3 4 -5
1 5 1
1 5 2
1 5 3
1 5 4
1 5 5

예제 출력 1

4
6
5
2
-3

출처

  • 문제를 번역한 사람: koosaga