Informatica Online Judge

  즐거운 텃밭 기르기 [2062 / 080E]

Time Limit(Test case) : 2000(ms)
Number of users who solved : 4   Total Tried : 6


The Champion of this Problem (C++) : gs15067 - 123ms / 2629byte
My Best Submission (C++) : N/A

[JOI 2015 Spring Camp (번역 : 31st 강한필)]

Background

텃밭의 프로 JOI군은, 매년 자신의 밭에서 IOI풀이라고 불리는 식물을 기르고 있다. 몇 개의 IOI풀은 가을이 되 면 아름다운 열매가 맺힌다. 열매가 맺힌 IOI풀은 수확된다. 열매가 맺히지 않은 IOI풀은 겨울이 되면 죽는다.

JOI군의 밭은 동서 방향으로 늘어선 N개의 구역으로 나뉘는데, 서쪽에서 i번째(1≤i≤N)인 구역 i에는 IOI풀 i가 심어져 있다. IOI풀 i는 봄에 키가 Hi까지 자라고 그 뒤로 자라지 않는다. IOI풀 i는 열매를 맺으면 Pi엔으로 거래된다. 열매를 맺지 않은 IOI풀은 시장에서 가치가 없다.

IOI풀은 여름에 햇빛을 많이 필요로 하는 식물이다. 한 구획에 심어져 있는 IOI풀에 대해, 그 구역보다 번호가 작은 구역과 번호가 큰 구역 모두에 그 IOI풀보다 키가 큰 IOI풀이 여름에 심어져 있으면, 그 IOI풀은 가을에 열매를 맺지 않는다.

즉 IOI풀 i(1≤i≤N)가 뽑히지 않을 때, 가을에 열매를 맺지 않는 것은 여름에서 구역 1, ⋯, i-1에 IOI풀 i 보다 큰 IOI풀이 있고, 구역 i+1, ⋯, N에 IOI풀 i보다 큰 IOI풀이 있는 경우이다.

열매를 맺은 IOI풀의 거래 가격의 합에서, IOI풀을 뽑는 데에 든 총 비용을 뺀 값이, JOI군의 이익이 된다. JOI 군은 IOI풀로부터 최대 얼마의 이익을 얻을 수 있을까?

Input

첫째 줄에는, 정수 N이 입력된다. N은 JOI군의 밭의 구역 수를 의미한다.

다음 N개의 줄의 i번째(1≤i≤N) 줄에는, 3개의 정수 Hi, Pi, Ci가 공백으로 구분되어 입력된다. 이것은, IOI풀 i가 봄에 키가 Hi까지 자란다는 것, 가을에 열매가 맺으면 가격이 Pi인 것, 그리고 뽑는 비용은 Ci라는 것을 의미한다.

모든 입력 데이터는 다음의 조건을 만족한다.

* 3 ≤ N ≤ 1 00 000
* 1 ≤ Hi ≤ 1 000 000 000 (1≤i≤N)
* 1 ≤ Pi ≤ 1 000 000 000 (1≤i≤N)
* 1 ≤ Ci ≤ 1 000 000 000 (1≤i≤N)

[Sub-Task Info]
#1 : N <= 20 (10%)
#2 : N <= 300 (10%)
#3 : N <= 5000 (10%)
#4 : H의 원소들은 서로 다르다. (50%)
#5 : 제한 조건 없음. (20%)

Output

JOI군의 이익의 최댓값을 정수로 첫 번째 줄에 출력한다.

IO Example

입력1
7
22 60 30
46 40 30
36 100 50
11 140 120
38 120 20
24 90 60
53 50 20

출력1
320

입력2
5
18 150 180
18 380 250
18 140 170
17 180 900
14 150 520

출력2
1000

입력3
8
52 156 59
15 166 185
16 122 115
24 161 154
44 252 678
32 225 557
44 155 254
59 57 253

출력3
854

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]