시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 (추가 시간 없음) | 1024 MB | 1923 | 743 | 620 | 41.306% |
눈송이들이 많은 동네인 숙명여대 앞마당에서 눈사람 만들기 대회를 연다. 앞마당의 길이는 $N$이고 위치 $1$부터 위치 $N$ 까지만 눈이 쌓여있다. 위치 $i$에 눈이 $a_i$만큼 쌓여있다. 대회 규칙은 해당 앞마당에서 $M$초 동안 눈덩이를 굴려 눈사람을 만드는 것이다. 눈덩이의 시작 크기는 $1$이다. 눈덩이의 시작 위치는 $0$이다.
가장 큰 눈사람을 만들고 싶던 수수는 눈덩이를 굴리는 법을 연구했다. 눈덩이를 굴리는 방법에는 두 가지가 있다. 눈덩이를 굴리거나 던질 때 1초가 소모된다.
눈덩이가 앞마당의 끝에 도달한 경우 남은 시간과 관계없이 눈덩이 굴리기는 끝이 난다. 대회 시간 내에 가장 크게 만들 수 있는 눈덩이의 크기를 구하는 프로그램을 작성해보자.
첫째 줄에 공백을 기준으로 앞마당의 길이 $N$ ($1 \leq N \leq 100$), 대회의 시간 $M$ ($1 \leq M \leq 10$)이 주어진다.
둘째 줄에 길이가 $N$인 수열 $a$가 주어진다. ($1 \leq a_i \leq 1\,000\,000$)
첫째 줄에 대회 시간 내에 가장 크게 만들 수 있는 눈덩이의 크기를 출력한다.
10 5 1 3 4 5 6 7 8 10 12 14
28