레이팅 미적용농부 존은 최근 착유기 N대 (1 <= N <= 40,000)가 들어 있는 새 축사를 구입했다. 착유기에는 편의상 1..N의 번호가 붙어 있으며 한 줄로 배치되어 있다.
착유기 i는 하루에 M(i) 단위의 우유를 짜낼 수 있다 (1 <= M(i) <= 100,000). 안타깝게도 착유기들이 너무 가깝게 설치되어 있어서, 어떤 날에 착유기 i를 사용하면 그날 양옆의 이웃한 두 착유기는 사용할 수 없다 (끝에 있는 착유기는 이웃이 하나뿐이다). 농부 존은 날마다 다른 착유기 부분집합을 골라 가동할 수 있다.
농부 존은 D일 (1 <= D <= 50,000)에 걸쳐 짜낼 수 있는 우유의 최대량을 계산하고 싶어 한다. 매일 아침 그는 착유기 하나를 골라 정비할 시간이 있으며, 이를 통해 그날부터 그 착유기의 일일 우유 생산량 M(i)를 바꿀 수 있다. 이러한 일별 변경 목록이 주어질 때, D일 동안 생산할 수 있는 우유의 양을 농부 존에게 알려주시오 (이 수는 32비트 정수 범위를 벗어날 수 있다).
첫째 줄에 N과 D의 값이 주어진다.
둘째 줄부터 1+N번째 줄까지, i+1번째 줄에 M(i)의 초깃값이 주어진다.
2+N번째 줄부터 1+N+D번째 줄까지, 1+N+d번째 줄에 두 정수 i와 m이 주어지며, 이는 농부 존이 d일째 되는 날 아침에 M(i)의 값을 m으로 갱신함을 나타낸다.
FJ가 D일 동안 생산할 수 있는 우유의 최대 총량을 출력한다.
optmilk.in · 출력을 쓸 파일 optmilk.out5 3
1
2
3
4
5
5 2
2 7
1 1032Output details: Day 1 optimum is 6, day 2 is 11, day 3 is 15, total 32.
riseoj 작성
출처 올림피아드 > USACO > 2013-2014 > December > Gold