페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#5653
서브태스크

블록 쌓기 2s 1024MB

문제

블록을 쌓는 놀이를 하고 있다. 블록을 위로 쌓을 수 있는 칸들이 총 N개 있으며, 1번 칸부터 N번 칸까지 순서대로 붙어 있다.

현재 i번 칸에는 A_i개의 블록이 쌓여 있다. 현재 블록들이 쌓인 모양이 난잡하다고 생각해, 다음과 같은 조건들을 만족하도록 블록들을 옮기려고 한다.

1. 각 칸에 쌓인 블록의 개수는 L 이상 R 이하이다.

2. 각 칸에 쌓인 블록의 개수는 단조증가한다: 1≤i≤N−1에 대해 i번 칸에 쌓인 블록의 개수는 i+1번 칸에 쌓인 블록의 개수 이하이다.

여러분은 어떠한 칸의 블록을 인접한 칸으로 옮기는 것을 반복해 목표를 달성하려고 한다. 목표를 달성하는 것이 가능한지 판별하고, 가능한 경우 블록을 옮기는 횟수의 최솟값을 구해야 한다.


입력

첫 번째 줄에 N, L, R이 공백으로 구분되어 주어진다.

두 번째 줄에 A_1, …, A_N 이 공백으로 구분되어 주어진다.​​ 

[제약 조건]

1 ≤ N ≤ 100

0 ≤ L ≤ R ≤ 10^9

R − L ≤ 100

0 ≤ A_i ≤ 10^9 ​(1 ≤ i ≤ N)

주어지는 수는 모두 정수이다.


출력

목표를 달성하는 것이 불가능하다면  -1을 출력한다. 

목표를 달성하는 것이 가능하다면 블록을 옮기는 횟수의 최솟값을 출력한다.​ 


부분문제

번호 점수 조건
#17점

N≤50, R−L≤1

#26점

N≤4, R−L≤50

#311점

N≤10, A_1+⋯+A_N≤10

#411점

N≤50, A_1+⋯+A_N≤50​

#530점

N≤50, R≤50

#610점

N≤50, R−L≤50

#725점

추가 제약 조건 없음.​


예제 #1

5 3 5

2 0 9 1 4
7

예제 #2

10 3 8

2 7 9 10 2 2 2 8 3 8
25

예제 #3

10 6 7

10 7 5 4 4 3 9 4 9 7
20

예제 #4

3 2 3

1 1 1
-1

출처

KOI 1차 2023 고3
로그인해야 코드를 작성할 수 있어요.