수열과 쿼리 33
시간 제한5초메모리 제한512 MB
부분 배열마다 서로 겹치지 않는 비어 있지 않은 연속 구간 k개를 골라 원소 합의 최댓값을 구한다.
문제
길이가 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)
출력
쿼리의 결과를 한 줄에 하나씩 출력한다.