월향 수목원

시간 제한3.5초메모리 제한1024 MB

요약
각 식물은 영양분 A_i를 필요로 하고 매일 1씩 받으며, 다 자란 뒤에는 반경 R_i 안의 식물에 매일 V_i를 공급할 때 모든 식물이 성장을 마치는 최소 일수를 구한다.
난이도

어려움10점 중 9점

유형
이분 탐색, 누적 합, 시뮬레이션, 구현
정답자
아직 제출이 없습니다

문제

월향 수목원은 최근 NN개의 식물을 심었다. 초기에 식물들은 아직 영양분을 받지 못한 상태다.

ii번 식물은 A_iA\_i 만큼의 영양분을 받으면 완전히 성장하며, 완전히 성장한 다음 날부터 구간 \[max⁡(1,i−R_i),min⁡(N,i+R_i)]\[\max(1,i-R\_i),\min(N,i+R\_i)]에 속한 식물들에 영양분을 매일 V_iV\_i 만큼 공급하기 시작한다.

월향 수목원의 관리자인 아이보리가 매일 모든 식물에 11만큼의 영양분을 준다고 할 때, 모든 식물이 완전히 성장하기 위해서는 적어도 며칠이 걸리는지 구해보자.

입력

첫째 줄에 정수 NN이 주어진다. (1≤N≤200,000)(1\leq N \leq 200\\,000)

둘째 줄부터 NN개의 줄에 걸쳐 정수 A_i,R_i,V_iA\_i, R\_i, V\_i 가 공백으로 구분되어 주어진다. (1≤A_i,V_i≤200,000;1≤R_i≤N)(1 \leq A\_i, V\_i \leq 200\\,000; 1\leq R\_i \leq N)

출력

모든 식물이 완전히 성장하는 데 필요한 최소 일수를 출력한다.

예제2

  1. 예제 1

    입력
    4
1 3 1
2 1 1
3 1 1
5 1 1
    예상 출력
    3

  2. 예제 2

    입력
    10
17 1 4
6 4 5
19 3 4
3 4 2
4 4 5
9 4 1
8 2 3
3 3 3
3 4 1
2 1 2
    예상 출력
    5