Fișierul intrare/ieșire decupare.in, decupare.out Sursă ad-hoc
Autor Cătălin Frâncu Adăugată de avatar Catalin.Francu Cătălin Frâncu Catalin.Francu
Timp de execuție pe test 0.2 sec Limită de memorie 2048 KB
Scorul tău N/A Dificultate N/A
open book Poți vedea testele pentru această problemă accesând atașamentele .

Decupare

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:

  • cele trei numere să nu se suprapună;
  • suma celor trei numere să fie maximă.

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, fără spații sau alte caractere.

Date de ieșire

În fișierul de ieșire decupare.out se va scrie suma maximă găsită.

Restricții

  • 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

Exemplu

decupare.in decupare.out Explicație
8 2
26341678
182
numerele care produc suma maximă sunt 63, 41 și 78
13 3
2937278963217
2358
numerele care produc suma maximă sunt 937, 789 și 632

Trebuie să te autentifici pentru a trimite soluții. Click aici

Indicii de rezolvare

Arată 3 categorii