CSES - Datatähti 2019 alku - Taulukko
- Time limit: 1.00 s
- Memory limit: 512 MB
Annettuna on taulukko, jossa on n lukua. Monessako taulukon yhtenäisessä osataulukossa on enintään k eri lukua?
Syöte
Syötteen ensimmäisellä rivillä on kaksi kokonaislukua n ja k: taulukon koko ja suurin sallittu määrä eri lukuja osataulukossa.
Seuraavalla rivillä on n kokonaislukua x1,x2,…,xn: taulukon sisältö.
Tuloste
Tulosta yksi kokonaisluku: tehtävän vastaus.
Esimerkki 1
Syöte:
5 2
1 2 3 1 1
Tuloste:
10
Esimerkki 2
Syöte:
8 1
1 1 1 1 1 1 1 1
Tuloste:
36
Osatehtävä 1 (12 pistettä)
- 1≤k≤n≤100
- 1≤xi≤10
Osatehtävä 2 (35 pistettä)
- 1≤k≤n≤5000
- 1≤xi≤106
Osatehtävä 3 (18 pistettä)
- 1≤k≤n≤5⋅105
- 1≤k≤2
- 1≤xi≤109
Osatehtävä 4 (35 pistettä)
- 1≤k≤n≤5⋅105
- 1≤xi≤109