시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 128 MB | 2661 | 792 | 557 | 29.393% |
화영이는 고대 유적을 탐사하던 도중 보석을 발견했다. 유적 속에는 N(1 ≤ N ≤ 100,000)개의 보석들이 일렬로 놓여 있었다. 각각의 보석의 가치는 다를 수 있기 때문에, 화영이는 가급적 많은 이득을 얻을 수 있도록 보석을 가져가려 한다. 이때, 다음 세 가지의 조건이 만족되어야 한다.
보석들의 개수가 매우 많기 때문에, 화영이는 이 문제를 컴퓨터를 이용하여 풀기로 하였다. 보석들에 대한 정보가 주어졌을 때, 위의 조건들을 만족하면서 이동할 때 얻을 수 있는 가치의 총 합의 최댓값을 구하는 프로그램을 작성하시오.
첫째 줄에 두 정수 N, M이 주어진다. 다음 N개의 줄에는 차례로 각 보석의 가치가 주어진다. 각 보석의 가치의 절댓값은 2,000이하의 정수이다.
첫째 줄에 가치의 총 합의 최댓값을 출력한다.
8 4 -1 -1 1 1 1 1 -1 2
5