CSES - Datatähti 2017 alku - Maalarit
  • Time limit: 2.00 s
  • Memory limit: 512 MB

Uolevin aita muodostuu nn laudasta, joista jokaisella on tietty korkeus. Uolevi haluaa maalauttaa aidan niin, että mitkään kaksi vierekkäistä lautaa eivät ole samanväriset.

Maalausta varten Uolevi palkkaa joukon maalareita. Jokainen maalari maalaa yhden tai useamman laudan omalla värillään. Kunkin maalarin palkkio on suurin hänen maalaamansa laudan korkeus.

Tehtäväsi on etsiä tapa maalata aita niin, että maalarien yhteispalkkio on mahdollisimman pieni. Saat päättää itse, montako maalaria palkkaat.

Syöte

Syötteen ensimmäisellä rivillä on luku nn: lautojen määrä.

Seuraavalla rivillä on nn kokonaislukua x1,x2,,xnx_1,x_2,\ldots,x_n: lautojen korkeudet.

Tuloste

Tulosta ensin kokonaisluvut cc ja kk: maalauksen pienin mahdollinen kustannus ja montako maalaria palkataan (1kn1 \le k \le n).

Tulosta sitten rivi, joka kertoo, kuka maalari maalaa minkäkin laudan. Rivillä tulee olla nn kokonaislukua väliltä 1k1 \ldots k.

Voit tulostaa minkä tahansa kelvollisen ratkaisun, jossa yhteispalkkio on pienin mahdollinen.

Esimerkki

Syöte:

6
5 8 3 2 7 2

Tuloste:

15 3
1 2 1 3 2 3

Selitys: Maalarin 11 palkkio on 55, maalarin 22 palkkio on 88 ja maalarin 33 palkkio on 22. Niinpä yhteispalkkio on 1515, joka on pienin mahdollinen.

Maalattu aita näyttää tältä:

Osatehtävä 1 (12 pistettä)

  • 1n101 \le n \le 10
  • 1xi1001 \le x_i \le 100

Osatehtävä 2 (25 pistettä)

  • 1n1001 \le n \le 100
  • 1xi1001 \le x_i \le 100

Osatehtävä 3 (31 pistettä)

  • 1n1001 \le n \le 100
  • 1xi1091 \le x_i \le 10^9

Osatehtävä 4 (32 pistettä)

  • 1n1051 \le n \le 10^5
  • 1xi1091 \le x_i \le 10^9