Moldovan Robert (use KN) (moldovan_robert_lol) Cerința
Gug pregătește un festin pentru prietenii săi. Festinul constă în \(N\) mâncăruri aranjate într-un rând. Mâncarea \(i\) dă valoarea de satisfacție \(A_i\) când este consumată. Cum unele mâncăruri pot fi expirate, ele pot avea valoarea de satisfacție \(A_i\) negativă.
Există un total de \(K\) persoane care participă la festin și fiecărei persoană îi va fi desemnată o secvență de mâncăruri pe care le poate consuma. Această secvență poate fi și goală. Două secvențe nu se pot suprapune, fiindcă mâncarea nu poate fi consumată de mai multe ori. Gug dorește să aleagă secvențele de mâncăruri pentru fiecare persoană în așa fel încât valoarea totală de satisfacție să fie maximizată.
Date de intrare
Pe prima linie se vor afla numerele \(N\) și \(K\), cu semnificația din enunț.
Pe a doua linie se vor afla \(N\) numere întregi, reprezentând elementele șirului.
Date de ieșire
Se va afișa suma maximă care se poate obține alegând maxim \(K\) secvențe disjuncte.
Restricții și precizări
- Se recomandă folosirea fastio
- \(1 \leq K \leq N \leq 3 \cdot {10}^{5}\)
- \(0 \leq |A_i| \leq {10}^{9}\)
Subtask-uri
| Subtask | Puncte | Restricții suplimentare |
1 (testele 1-10) |
4 |
\(A_i \geq 0\) |
2 (testele 11-20) |
8 |
\(\vert S \vert = 1, S = \left\{ i, A_i < 0 \right\}\) |
3 (testele 21-30) |
18 |
\(K = 1\) |
4 (testele 31-40) |
10 |
\(1 \leq K \leq N \leq 80\) |
5 (testele 41-50) |
11 |
\(1 \leq K \leq N \leq 300\) |
6 (testele 51-60) |
20 |
\(1 \leq K \leq N \leq 2 \ 000\) |
7 (testele 61-70) |
29 |
Nicio restricție suplimentară |
0 (testele 71-73) |
0 |
Exemple |
Exemplu 1:
Intrare
6 1 1 -2 3 -1 5 -6
Ieșire
7
Explicație
Soluția optimă este să alegem secvența \([3, \ -1, \ 5]\), obținând astfel suma \(7\).
Exemplu 2:
Intrare
6 2 1 2 3 -10 5 6
Ieșire
17
Explicație
Soluția optimă este să alegem secvențele \([1, \ 2, \ 3]\) și \([5, \ 6]\), obținând astfel suma \(17\).
Exemplu 3:
Intrare
6 4 -1 -2 -1 0 -5 -1
Ieșire
0
Explicație
Fiindcă toate secvențele au sumă non-pozitivă, este optim să nu alegem nicio secvență, obținând astfel suma \(0\).