#CW23. 红色(red)

红色(red)

题目描述

有一个长度为 nn 的数组。一个位置最多会有红、绿、蓝三种颜色,最少会有一种颜色。

第 ii 个位置由三个整数 ai,bi,cia_i,b_i,c_i 描述,分别表示该位置是否具有红、绿、蓝这三种颜色。

对于一个连续区间 [l,r][l,r],定义其中三种颜色的数量:

$$R=\sum_{i=l}^{r}a_i,\quad G=\sum_{i=l}^{r}b_i,\quad B=\sum_{i=l}^{r}c_i.$$

若满足 R≥GR \ge G 且 R≥BR \ge B,则称区间 [l,r][l,r] 为红色区间。

现在请将整个数组划分为若干个非空连续区间。

一次划分的得分为:所有被划分出的红色区间的长度之和。

注意,非红色区间的长度不计入得分,但它仍然可以是划分的一部分。

求所有划分方案中的最大得分。

输入格式

第一行包含一个整数 nn。

接下来 nn 行,每行包含三个整数 ai,bi,cia_i,b_i,c_i,表示第 ii 个位置的三种颜色信息。

输出格式

输出一个整数,表示最大得分。

样例 1 输入

6
0 1 0
0 0 1
1 0 1
1 0 0
0 1 0
0 0 1

样例 1 输出

5

样例 1 解释

可以将前五个位置划为一个区间、最后一个位置单独划为一个区间。

数据范围

对于所有测试数据,保证:1≤n≤1061 \le n \le 10^6,0≤ai,bi,ci≤10 \le a_i,b_i,c_i \le 1,1≤ai+bi+ci≤31 \le a_i+b_i+c_i \le 3。

测试点 n≤n \le 特殊性质
1∼41 \sim 4 2020 无
5∼85 \sim 8 10001000
9∼139 \sim 13 10610^6 ci=0c_i=0
14∼1614 \sim 16 6000060000 无
17∼2017 \sim 20 10610^6