Maalarit |
| Time limit: | 2.00 s |
| Memory limit: | 512 MB |
|
Uolevin aita muodostuu $n$ 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 $n$: lautojen määrä.
Seuraavalla rivillä on $n$ kokonaislukua $x_1,x_2,\ldots,x_n$: lautojen korkeudet.
Tuloste
Tulosta ensin kokonaisluvut $c$ ja $k$: maalauksen pienin mahdollinen kustannus ja montako maalaria palkataan ($1 \le k \le n$).
Tulosta sitten rivi, joka kertoo, kuka maalari maalaa minkäkin laudan. Rivillä tulee olla $n$ kokonaislukua väliltä $1 \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 $1$ palkkio on $5$, maalarin $2$ palkkio on $8$ ja maalarin $3$ palkkio on $2$. Niinpä yhteispalkkio on $15$, joka on pienin mahdollinen.
Maalattu aita näyttää tältä:
Osatehtävä 1 (12 pistettä)
- $1 \le n \le 10$
- $1 \le x_i \le 100$
Osatehtävä 2 (25 pistettä)
- $1 \le n \le 100$
- $1 \le x_i \le 100$
Osatehtävä 3 (31 pistettä)
- $1 \le n \le 100$
- $1 \le x_i \le 10^9$
Osatehtävä 4 (32 pistettä)
- $1 \le n \le 10^5$
- $1 \le x_i \le 10^9$
