NOI '15 P5 - Cocktail Party

View as PDF

Submit solution

Points: 25 (partial)
Time limit: 1.0s
Memory limit: 512M

Problem types

You are given a string of length n representing the labels of n cups of cocktail. The i-th cup of cocktail has label s_i, and the labels are among the 26 lowercase English letters. Let \mathrm{Str}(l,r) = s_l s_{l+1} \cdots s_r be the string formed by the labels of the cocktails from the l-th cup to the r-th cup. If \mathrm{Str}(p,p_0) = \mathrm{Str}(q,q_0) where 1 \le p \le p_0 \le n, 1 \le q \le q_0 \le n, p \ne q, p_0-p+1 = q_0-q+1 = r, we say the p-th cup of cocktail and q-th cup of cocktail are r-similar. Of course, for two cups of cocktail that are r-similar (r > 1) they are also 1-similar, 2-similar, ..., and (r-1)-similar. In particular, for any 1 \le p \le q \le n, p \ne q, the p-th cup of cocktail and q-th cup of cocktail are 0-similar.

Freda assigns the "deliciousness" for each cup of cocktail, and the i-th cup has deliciousness a_i. If we mix p-th cup of cocktail and q-th cup of cocktail, we may obtain cocktail with deliciousness a_p a_q. The problem asks for each r = 0,\dots,n-1, how many ways we may select two cups of cocktail that are r-similar, and compute the maximum possible deliciousness by mixing two cups of cocktail that are r-similar.

Input Specification

The first line of the input contains an integer n denoting the number of cups of cocktail. The second line contains a string S with length n such that the i-th character denotes the label of the i-th cup of cocktail. The third line contains n integers separated by a single space such that the i-th integer denotes the i-th cup of cocktail has deliciousness a_i.

Output Specification

The output contains n lines. The i-th line contains two integers separated by a single space. The first integer denotes the number of ways to choose two cups of (i-1)-similar cocktails. The second integer denotes the maximum possible deliciousness by mixing two cups of cocktails that are (i-1)-similar. Notice if there does not exist two cups of cocktail that are (i-1)-similar, both integers in that line of the output shall be 0.

Sample Input 1

10
ponoiiipoi
2 1 4 7 4 8 3 6 4 7

Sample Output 1

45 56
10 56
3 32
0 0
0 0
0 0
0 0
0 0
0 0
0 0

Sample Input 2

12
abaabaabaaba
1 -2 3 -4 5 -6 7 -8 9 -10 11 -12

Sample Output 2

66 120
34 120
15 55
12 40
9 27
7 16
5 7
3 -4
2 -4
1 -4
0 0
0 0

Constraints

Test Casena_iAdditional Constraints
1n = 100|a_i| \le 10\,000
2n = 200
3n = 500
4n = 750
5n = 1000|a_i| \le 1\,000\,000\,000
6
7n = 2000
8
9n = 99\,991|a_i| \le 1\,000\,000\,000There will not exist 10-similar cocktails.
10
11n = 100\,000|a_i| \le 1\,000\,000All a_i are equal.
12n = 200\,000
13n = 300\,000
14
15n = 100\,000|a_i| \le 1\,000\,000\,000
16
17n = 200\,000
18
19n = 300\,000
20

Comments

There are no comments at the moment.