Problem
La cavalletta salta su colonne poste sulla stessa linea a uguale distanza l'una dall'altra. Le colonne hanno numeri di serie da 1 a N . All'inizio, la cavalletta siede su un palo con il numero 1. Può saltare in avanti da 1 a K barre, contando da quella attuale.
Su ogni colonna, la cavalletta può guadagnare o perdere diverse monete d'oro (questo numero è noto per ogni colonna). Determina come deve saltare la cavalletta per raccogliere il maggior numero di monete d'oro. Tieni presente che la cavalletta non può saltare all'indietro.
Inserimento:
- la prima riga contiene due numeri naturali: N e K (\(2 <= N ,\ K < = 10000\)), separati da spazio;
- nella seconda riga, N-2 interi separati da spazio – il numero di monete che il Grasshopper ottiene su ciascuna colonna, dalla 2a alla N-1a. Se questo numero è negativo, la cavalletta perde monete.
È garantito che tutti i numeri in modulo non superino 10000.
Risultato:
- nella prima riga, il programma dovrebbe visualizzare il numero massimo di monete che il Grasshopper può raccogliere;
- la seconda riga mostra il numero di salti di Grasshopper;
- sulla terza riga – numeri di tutte le colonne visitate da Grasshopper (separati da uno spazio in ordine crescente).
Se ci sono più risposte corrette, stampane qualcuna.
Esempi
| # |
Input |
Uscita |
| 1 |
5 3
2 -3 5
|
7
3
1 2 4 5
|