시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 512 MB 83 14 12 16.216%

문제

길이가 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

예제 입력 2

5 1
7 7 7 7 7
1 5 1

예제 출력 2

35
W3sicHJvYmxlbV9pZCI6IjE3ODIzIiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVjMjE4XHVjNWY0XHVhY2ZjIFx1Y2ZmY1x1YjlhYyAzMyIsImRlc2NyaXB0aW9uIjoiPHA+XHVhZTM4XHVjNzc0XHVhYzAwIE5cdWM3NzggXHVjMjE4XHVjNWY0IEE8c3ViPjE8XC9zdWI+LCBBPHN1Yj4yPFwvc3ViPiwgLi4uLCBBPHN1Yj5OPFwvc3ViPlx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuJm5ic3A7XHVjNzc0XHViNTRjLCBcdWIyZTRcdWM3NGMgXHVjZmZjXHViOWFjXHViOTdjIFx1YzIxOFx1ZDU4OVx1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LiZuYnNwOzxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPjxjb2RlPmwgciBrPFwvY29kZT46IFx1YmQ4MFx1YmQ4NFx1YzIxOFx1YzVmNCZuYnNwO0E8c3ViPmw8XC9zdWI+LCBBPHN1Yj5sKzE8XC9zdWI+LCAuLi4sIEE8c3ViPnI8XC9zdWI+Jm5ic3A7XHVjNWQwIFx1YjMwMFx1ZDU3NCwgXHVkNTc0XHViMmY5IFx1YmQ4MFx1YmQ4NCBcdWMyMThcdWM1ZjRcdWM1ZDBcdWMxMWMga1x1YWMxY1x1Yzc1OCBcdWJkODBcdWJkODQmbmJzcDtcdWMyMThcdWM1ZjRcdWM3NDQgXHVhY2U4XHViNzdjXHVjMTFjIFx1YmQ4MFx1YmQ4NCBcdWMyMThcdWM1ZjRcdWM3NTggXHVjNmQwXHVjMThjXHVjNzU4IFx1ZDU2OVx1Yzc1OCBcdWNkNWNcdWIzMTNcdWFjMTJcdWM3NDQgXHVjZDljXHViODI1XHVkNTU4XHViNzdjLiBcdWFjZTBcdWI5NzggXHViZDgwXHViZDg0IFx1YzIxOFx1YzVmNFx1Yzc0MCBcdWFjMDFcdWFjMDEgXHViZTQ0XHVjNWI0XHVjNzg4XHVjOWMwIFx1YzU0YVx1YzU0NFx1YzU3YyBcdWQ1NThcdWJhNzAsIFx1YzExY1x1Yjg1YyBcdWFjYjlcdWNjZDBcdWMxMWNcdWIyOTQgXHVjNTQ4XHViNDFjXHViMmU0LjxcL2xpPlxyXG48XC91bD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YzIxOFx1YzVmNFx1Yzc1OCBcdWQwNmNcdWFlMzAgTiwgXHVjZmZjXHViOWFjXHVjNzU4IFx1YWMxY1x1YzIxOCBNXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmxlOyBOLCBNICZsZTsgMzUsMDAwKTxcL3A+XHJcblxyXG48cD5cdWI0NThcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IEE8c3ViPjE8XC9zdWI+LCBBPHN1Yj4yPFwvc3ViPiwgLi4uLCBBPHN1Yj5OPFwvc3ViPlx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgtMzUsMDAwJm5ic3A7JmxlOyBBPHN1Yj5pPFwvc3ViPiZuYnNwOyZsdDsgMzUsMDAwKTxcL3A+XHJcblxyXG48cD5cdWMxNGJcdWM5ZjggXHVjOTA0XHViZDgwXHVkMTMwIE1cdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwXHViMjk0IFx1Y2ZmY1x1YjlhY1x1YWMwMCBcdWQ1NWMgXHVjOTA0XHVjNWQwIFx1ZDU1OFx1YjA5OFx1YzUyOSBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgbCAmbGU7IHImbmJzcDsmbGU7IE4sIDEgJmxlOyBrICZsZTsgciAtIGwgKyAxKTxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2ZmY1x1YjlhY1x1Yzc1OCBcdWFjYjBcdWFjZmNcdWI5N2MgXHVkNTVjIFx1YzkwNFx1YzVkMCBcdWQ1NThcdWIwOThcdWM1MjkgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjE3ODIzIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiSG9ub3JhYmxlIE1lbnRpb24iLCJkZXNjcmlwdGlvbiI6IjxwPklseWEgWmJhbiBoYXMgYW4gYXJyYXkgYTxzdWI+MTxcL3N1Yj4sIGE8c3ViPjI8XC9zdWI+LCAuIC4gLiAsIGE8c3ViPm48XC9zdWI+LiBBIHNlZ21lbnQgW2wgLiAuIC4gcl0gb2YgdGhlIGFycmF5IGlzIHRoZSBhcnJheSBhPHN1Yj5sPFwvc3ViPiwgYTxzdWI+bCsxPFwvc3ViPiwgLiAuIC4gLCBhPHN1Yj5yPFwvc3ViPi48XC9wPlxyXG5cclxuPHA+SWx5YSBoYXMgcSBvcmRlcmVkIHRyaXBsZXMgb2YgdGhlIGZvcm0gKGwsIHIsIGspLCB3aGVyZSAxICZsZTsgbCAmbGU7IHIgJmxlOyBuIGFuZCAxICZsZTsgayAmbGU7IHIgJm1pbnVzOyBsICsgMS4gRm9yIGVhY2ggc3VjaCB0cmlwbGUsIGhlIGFza2VkIHlvdSB0byBhbnN3ZXIgdGhlIGZvbGxvd2luZyBxdWVyeTogJmxkcXVvO3doYXQgaXMgdGhlIGxhcmdlc3Qgc3VtIG9mIHN1bXMgb2YgZWxlbWVudHMgb2YgayBub24tZW1wdHkgbm9uLWludGVyc2VjdGluZyBzdWJzZWdtZW50cyBvZiB0aGUgc2VnbWVudCBbbCAuIC4gLiByXT8mcmRxdW87LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgdHdvIGludGVnZXJzIG4gYW5kIHE6IHRoZSBudW1iZXIgb2YgZWxlbWVudHMgaW4gdGhlIGFycmF5IGFuZCB0aGUgbnVtYmVyIG9mIHF1ZXJpZXMgKDEgJmxlOyBuLCBxICZsZTsgMzUgMDAwKS48XC9wPlxyXG5cclxuPHA+VGhlIHNlY29uZCBsaW5lIGNvbnRhaW5zIG4gc3BhY2Utc2VwYXJhdGVkIGludGVnZXJzIGE8c3ViPjE8XC9zdWI+LCBhPHN1Yj4yPFwvc3ViPiwgLiAuIC4gLCBhPHN1Yj5uPFwvc3ViPjogdGhlIGdpdmVuIGFycmF5ICgmbWludXM7MzUgMDAwICZsZTsgYTxzdWI+aTxcL3N1Yj4gJmxlOyAzNSAwMDApLjxcL3A+XHJcblxyXG48cD5UaGUgbmV4dCBxIGxpbmVzIGNvbnRhaW4gcXVlcmllcy4gRWFjaCBvZiB0aGVtIGNvbnRhaW5zIHRocmVlIGludGVnZXJzIGwsIHIsIGs6IHRoZSBnaXZlbiBzZWdtZW50IGFuZCB0aGUgbnVtYmVyIG9mIG5vbi1pbnRlcnNlY3Rpbmcgc3Vic2VnbWVudHMgb24gaXQgdGhhdCB5b3Ugc2hvdWxkIGZpbmQgKDEgJmxlOyBsICZsZTsgciAmbGU7IG4sIDEgJmxlOyBrICZsZTsgciAmbWludXM7IGwgKyAxKS48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5PdXRwdXQgcSBpbnRlZ2VycyBvbiBzZXBhcmF0ZSBsaW5lczogdGhlIGFuc3dlcnMgdG8gdGhlIHF1ZXJpZXMuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

Camp > Petrozavodsk Programming Camp > Summer 2019 > Day 2 H번

  • 문제를 만든 사람: 300iq
  • 문제를 번역한 사람: koosaga