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

#3855

우유 생산(Optimal Milking) 1s 128MB

문제

농부 존은 최근 N개의 착유기가 있는 새로운 헛간을 구입했습니다 (1 <= N <= 40,000).

착유기의 번호는 왼쪽부터 오른쪽까지 순서대로 1 이상 N 이하의 정수 번호가 적혀있고, 착유기 i는 하루에 M(i) 단위의 우유를 추출할 수 있습니다 (1 <= M(i) <= 100,000).

농부 존은 매일 N개의 착유기 중 일부를 작동시켜 우유를 추출합니다. 안타깝게도 기계들이 너무 가까이 설치되어 있어서 기계 i를 작동시키고 있으면 인접한 두 기계는 그날 사용할 수 없습니다(양쪽 끝 기계에는 인접한 기계가 하나뿐입니다). 농부 존은 매일 작동할 기계의 목록을 조건에 맞게 자유롭게 선택할 수 있습니다.

농부 존은 일련의 D일 동안 추출할 수 있는 최대 우유량을 계산하는 데 관심이 있습니다 (1 <= D <= 50,000). 매일 아침, 농부 존은 착유기 i를 정비하면서 일일 우유 생산량 M(i)가 바뀝니다. 우유 생산은 착유기를 정비한 이후 시작합니다. 농부 존의 정비 계획을 바탕으로, 농부 존이 D일 동안 얼마나 많은 우유를 생산할 수 있는지 알려주십시오(정답은 32비트 정수 범위를 넘을 수 있습니다).


입력

첫 번째 줄에는 N과 D의 값이 주어집니다.

두 번째 줄부터 N개의 줄에는 i번째 착유기의 일일 생산량 M(i)가 주어집니다.

그 다음 줄부터 D개의 줄에는 정수 i, m이 주어지는데, 이는 농부 존이 d번째 날에 i번째 착유기의 일일 생산량 M(i)를 m으로 바꾼다는 것을 의미합니다.


출력

첫 번째 줄에 농부 존이 D일 동안 생산한 우유의 총량을 출력합니다.


예제 

5 3
1
2
3
4
5
5 2
2 7
1 10
32

입력 세부 정보

착유기 5대가 있으며, 초기 우유 생산량은 1, 2, 3, 4, 5입니다. 1일차에는 기계 5가 우유 2단위를 생산하도록 업데이트되고, 이런 식으로 반복되어 업데이트됩니다.

출력 세부 정보

첫째 날, 최적의 우유 생산량은 2+4=6(1+3+2로도 가능)입니다. 둘째 날, 최적의 생산량은 7+4=11입니다. 셋째 날, 최적의 생산량은 10+3+2=15입니다.



출처

USACO 2013 December Gold

로그인해야 코드를 작성할 수 있어요.