Diferențe pentru problema/decupare între reviziile #2 si #7

decupare

Decupare

== include(page="template/taskheader" task_id="decupare") ==

Se dă un vector format din $N$ cifre cuprinse între 1 și 9. Să se determine trei numere de exact $K$ cifre fiecare astfel încât:

Se dă o bandă de hârtie pe care sunt scrise $N$ cifre cuprinse între 1 și 9. Să se decupeze trei numere de exact $K$ cifre fiecare astfel încât:

* fiecare număr să corespundă unei secvențe continue de $K$ cifre din vector;
* cele trei secvențe să nu se suprapună;

* cele trei numere să nu se suprapună;

* suma celor trei numere să fie maximă.
h2. Date de intrare

Fișierul de intrare $decupare.in$ va conține:
* pe prima linie numerele $N$ și [$K$], despărțite printr-un spațiu;

* pe a doua linie cele $N$ cifre, nedespărțite prin nimic.

* pe a doua linie cele $N$ cifre, fără spații sau alte caractere.

h2. Date de ieșire

* $1 ≤ K ≤ 18$
* $3*K ≤ N ≤ 1.000.000$

* pentru 40% din teste, $N ≤ 100.000$
* pentru 30% din teste, $100.001 ≤ N ≤ 200.000$

h2. Exemplu
table(example).
|_. decupare.in |_. decupare.out |_. Explicație |
| 8 2

  26341678

26341678

| 182

| numerele care produc suma maximă sunt 63, 41 și 78
|

| numerele care produc suma maximă sunt 63, 41 și 78 |
| 13 3
2937278963217
| 2358
| numerele care produc suma maximă sunt 937, 789 și 632 |

== include(page="template/taskfooter" task_id="decupare") ==