시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
14 초 | 1024 MB | 35 | 20 | 17 | 56.667% |
Mona har just flyttat och ska nu börja inreda. Hon har kommit fram till att hon behöver precis $k$ stycken tavlor, och har åkt till konstmarknaden för att handla. Mona är väldigt rik, och bryr sig inte alls om hur mycket tavlorna kostar, utan vill istället bara bli färdig så snabbt som möjligt.
På marknaden säljs $N$ tavlor längs en lång gata. Tavla $i$ tar $t_i$ sekunder att köpa. Att gå från en tavla till nästa tar 1 sekund. Mona tar bussen dit och hem, så hon kan välja vid vilken tavla hon börjar och slutar. Vad är den kortaste tiden Mona kan köpa $k$ tavlor på?
Den första raden innehåller två heltal: $N$ ($1 \le N \le 2000$), antalet tavlor på marknaden, och $k$ ($1 \le k \le N$), antal tavlor Mona behöver köpa.
Den andra raden innehåller $N$ heltal: $1 \le t_1,t_2,...t_n \le 1000$, antal sekunder det tar att köpa respektive tavla.
Skriv ut ett heltal -- det minsta antalet sekunder det kan ta för Mona att köpa $k$ tavlor.
4 2 3 3 5 1
6
6 4 7 4 3 10 2 5
18
10 5 4 7 2 1 8 6 7 2 1 10
18
Olympiad > Swedish Olympiad in Informatics > 2021 > Online Qualification E번