

Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 点
問題文
この問題は C 問題の強化版です。分割する個数が 個になります。
長さ の整数列 が与えられます。
を か所で区切って 個の空でない連続する部分列に分割するとき、数列に含まれる数の種類数の和としてありえる最大値を求めてください。
より厳密には、 を満たす整数の組 について のそれぞれに含まれる整数の種類数の和としてありえる最大値を求めてください。
制約
- ()
- 入力はすべて整数である
入力
入力は以下の形式で標準入力から与えられる。
出力
答えを出力せよ。
入力例 1Copy
5 3 1 4 1 5
出力例 1Copy
5
とし、 と と の つの連続する部分列に分割すると、それぞれに含まれる整数の種類数は でこれらの和は です。また、 より大きい値は取り得ないので、答えは です。他にも、 などでも種類数の和は になります。
入力例 2Copy
10 2 5 6 4 4 1 1 3 1 4
出力例 2Copy
9
Score : points
Problem Statement
This problem is a harder version of Problem C. Here, the sequence is split into three subarrays.
You are given an integer sequence of length : .
When splitting at two positions into three non-empty (contiguous) subarrays, find the maximum possible sum of the counts of distinct integers in those subarrays.
More formally, find the maximum sum of the following three values for a pair of integers such that : the count of distinct integers in , the count of distinct integers in , and the count of distinct integers in .
Constraints
- ()
- All input values are integers.
Input
The input is given from Standard Input in the following format:
Output
Print the answer.
Sample Input 1Copy
5 3 1 4 1 5
Sample Output 1Copy
5
If we let to split the sequence into three subarrays , , , the counts of distinct integers in those subarrays are , , , respectively, for a total of . This sum cannot be greater than , so the answer is . Other partitions, such as , also achieve this sum.
Sample Input 2Copy
10 2 5 6 4 4 1 1 3 1 4
Sample Output 2Copy
9