시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 512 MB | 10600 | 3759 | 2887 | 37.156% |
아래와 같이 좌우로 $N$개의 장소가 있다.
장소들 중 서로 다른 두 곳을 골라서 벌을 한 마리씩 둔다. 또, 다른 한 장소를 골라서 벌통을 둔다. 아래 그림에서 연한 회색의 장소는 벌이 있는 장소이고 진한 회색의 장소는 벌통이 있는 장소이다.
두 마리 벌은 벌통으로 똑바로 날아가면서 지나가는 모든 칸에서 꿀을 딴다. 각 장소에 적힌 숫자는 벌이 지나가면서 꿀을 딸 수 있는 양이다.
위의 그림과 같이 배치된 경우 두 마리의 벌 모두 $4 + 1 + 4 + 9 + 9 = 27$의 꿀을 따서, 전체 꿀의 양은 54가 된다.
위의 그림과 같이 배치된 경우 왼쪽 장소에서 출발한 벌은 $9 + 4 + 4 + 9 + 9 = 35$의 꿀을 따고 오른쪽 장소에서 출발한 벌은 $4 + 9 + 9 = 22$의 꿀을 따므로, 전체 꿀의 양은 $57$이 된다.
위의 그림과 같은 경우는 전체 꿀의 양이 31이 된다.
장소들의 꿀 양을 입력으로 받아 벌들이 딸 수 있는 가능한 최대의 꿀의 양을 계산하는 프로그램을 작성하라.
첫 번째 줄에 장소의 수 $N$이 주어진다.
다음 줄에 왼쪽부터 각 장소에서 꿀을 딸 수 있는 양이 공백 하나씩을 사이에 두고 주어진다.
첫 번째 줄에 가능한 최대의 꿀의 양을 출력한다.
번호 | 배점 | 제한 |
---|---|---|
1 | 11 | $N \le 20$ |
2 | 13 | $N \le 500$ |
3 | 31 | $N \le 5~000$ |
4 | 45 | 추가적인 제한이 없음. |
7 9 9 4 1 4 9 9
57
7 4 4 9 1 9 4 4
54
3 2 5 4
10
Olympiad > 한국정보올림피아드 > KOI 2021 1차대회 > 중등부 1번