815 . 佳佳刷油漆

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

aacpschool

User's AC Ratio

100.0% (2/2)

Submission's AC Ratio

50.0% (2/4)

Tags

apcsc apcsc-dp

Description

佳佳不但最喜歡、而且也很擅長刷油漆，因此每當大家有需求都會請佳佳來幫忙刷油漆，然而這次上門的顧客有個特別的需求：

  • 他將家中長廊分成了 $N$ 個區段，他希望佳佳一個區段用一種顏色粉刷。
  • 相鄰的兩區段顏色不可以相同，畢竟這樣就看不出區段的交界處了。
  • 他只喜歡庚斯博羅灰、納瓦霍白以及韋奇伍德瓷藍這三種顏色，因此要求佳佳僅以這三種顏色粉刷。
  • 他在每個區段都會對三種顏色進行標價，佳佳會依照他在該區段粉刷的顏色獲得相應的報酬。

為了籌措出國留學所需要的經費，他希望你可以幫忙他找出能讓他獲得最多報酬的方法。

Input Format

輸入首行有一個正整數 $N$ ，代表顧客走廊的區段數量。
接下來有 $N$ 行，每行有三個整數，當中的第 $i$ 行的三個整數 $a_i, b_i, c_i$ 分別代表在第 $i$ 個區段上粉刷庚斯博羅灰、納瓦霍白、韋奇伍德瓷藍可以獲得的報酬。

  • $1 \le N \le 10^ 6$
  • $1 \le a_i, b_i, c_i \le 10^ 4$

Output Format

請輸出一個整數代表佳佳可以獲得的最大報酬。

Sample Input 1

3
10 40 70
20 50 80
30 60 90

Sample Output 1

210

Sample Input 2

1
100 10 1

Sample Output 2

100

Sample Input 3

7
6 7 8
8 8 3
2 5 2
7 8 6
4 6 8
2 3 4
7 5 1

Sample Output 3

46

Hints

Problem Source

AtCoder

Subtasks

No. Testdata Range Constraints Score
1 0~2 範例測資 0
2 0~22 無額外限制 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 524288 65536 1 2
1 1000 524288 65536 1 2
2 1000 524288 65536 1 2
3 1000 524288 65536 2
4 1000 524288 65536 2
5 1000 524288 65536 2
6 1000 524288 65536 2
7 1000 524288 65536 2
8 1000 524288 65536 2
9 1000 524288 65536 2
10 1000 524288 65536 2
11 1000 524288 65536 2
12 1000 524288 65536 2
13 1000 524288 65536 2
14 1000 524288 65536 2
15 1000 524288 65536 2
16 1000 524288 65536 2
17 1000 524288 65536 2
18 1000 524288 65536 2
19 1000 524288 65536 2
20 1000 524288 65536 2
21 1000 524288 65536 2
22 1000 524288 65536 2
Submit
Back to Top