시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
5 초 | 512 MB | 293 | 39 | 27 | 21.951% |
길이가 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)
쿼리의 결과를 한 줄에 하나씩 출력한다.
5 5 -1 2 -3 4 -5 1 5 1 1 5 2 1 5 3 1 5 4 1 5 5
4 6 5 2 -3
5 1 7 7 7 7 7 1 5 1
35