레이팅 미적용베시는 무루(Mooloo)에서 방송을 보는 것을 좋아한다. 베시는 바쁜 소라서, 앞으로 무루를 시청할 \(N\) (\(1 \leq N \leq 10^5\))일의 일정을 계획해 두었다. 무루는 유료 구독 서비스이므로, 이제 베시는 내야 할 돈을 최소화하는 방법을 정해야 한다.
무루의 구독 체계는 흥미롭다. \(d\)일 연속으로 무루를 구독하는 데 \(d + K\) (\(1\le K\le 10^9\)) 무니가 든다. 구독은 아무 때나 시작할 수 있고, 현재 구독이 만료되면 원하는 만큼 여러 번 새로 구독을 시작할 수 있다. 이때 베시가 일정을 모두 소화하기 위해 내야 하는 무니의 최소량을 구한다.
출제자: Danny Mittal
배점
- 입력 3-5: \(N \le 10\)
- 입력 6-12: 추가 제약이 없다.
출제자: Danny Mittal
첫째 줄에 정수 \(N\)과 \(K\)가 주어진다.
둘째 줄에 베시가 무루를 시청할 날들을 나타내는 \(N\)개의 정수 \(1\le d_1
이 문제에서 다루는 정수의 크기가 크므로 64비트 정수 자료형(예: C/C++의 "long long")이 필요할 수 있음에 유의한다.
2 4
7 97Bessie buys a three-day subscription on day 7, spending \(d+K = 3 + 4 = 7\)
moonies.
2 3
1 108Bessie first buys a one-day subscription on day 1, spending \(d+K = 1+3 = 4\)
moonies. Bessie also buys a one-day subscription on day 10, spending
\(d+K = 1+3 = 4\) moonies. In total, Bessie spends 8 moonies.
riseoj 작성
출처 올림피아드 > USACO > 2022-2023 > February > Bronze