Simulare OJI 2016 cls a 8-a | ks

This was the problem page during the contest. Access the current page here.
Time limit: 0.2s Memory limit: 4MB Input: ks.in Output: ks.out

Ana și Bogdan au inventat din nou un joc, pe care l-au denumit ks. Pe tabla de joc sunt plasate pe poziții consecutive nn jetoane, pe fiecare jeton fiind scris un număr natural nenul. Ana este prima la mutare și are voie să extragă de pe tablă exact kk jetoane situate pe poziții consecutive.

Bogdan mută al doilea și are și el voie să extragă exact kk jetoane, dintre cele rămase pe tablă, situate de asemenea pe poziții consecutive.

Punctajul asociat unei mutări este egal cu suma numerelor scrise pe jetoanele extrase la mutarea respectivă.

Scopul Anei este să efectueze mutarea sa astfel încât punctajul obținut de Bogdan să fie cât mai mic. Considerăm că atât Ana, cât și Bogdan joacă optim.

Cerință

Cunoscând numărul de jetoane de pe tabla de joc, valorile înscrise pe acestea, precum și valoarea kk, scrieți un program care să determine care este cel mai bun punctaj pe care Bogdan îl poate obține, știind că ambii jucători joacă optim.

Date de intrare

Fișierul de intrare ks.in conține pe prima linie două numere naturale separate prin spațiu n kn \ k, având semnificația din enunț. Pe cea de a doua linie se află nn valori naturale nenule, separate prin câte un spațiu, reprezentând valorile înscrise pe cele nn jetoane, în ordinea în care acestea sunt plasate pe tabla de joc.

Date de ieșire

Fișierul de ieșire ks.out va conține o singură linie pe care va fi scris un număr natural reprezentând punctajul maxim pe care îl poate obține Bogdan la mutarea sa, știind că ambii jucători joacă optim.

Restricții și precizări

  • 3n100 0003 \leq n \leq 100 \ 000;
  • 1kn/31 \leq k \leq n/3;
  • Valorile înscrise pe jetoane sunt numere naturale nenule 109\leq 10^9;
  • După ce Ana extrage jetoanele sale, jetoanele rămase pe tablă își vor păstra pozițiile inițiale.

Exemplu

ks.in

10 3
1 2 5 4 15 2 4 5 1 6

ks.out

12

Explicație

Există mai multe mutări optime pentru Ana. Una dintre acestea este de a selecta jetoanele 5,4,155, 4, 15.

În acest caz cea mai bună mutare pentru Bogdan este de a selecta jetoanele 5,1,65, 1, 6 care i-ar aduce un punctaj egal cu 1212, maxim posibil. O altă mutare optimă pentru Ana este de a alege jetoanele 4,15,24, 15, 2, sau 15,2,415, 2, 4, punctajul maxim pe care îl poate obține Bogdan rămânând același, 1212.

Log in or sign up to be able to send submissions!