[Codeforces Round #321] A-E

10
24
2015

这场A-D很水，就E难一点，就全部放在同一篇题解里了。

Kefa decided to make some money doing business on the Internet for exactly n days. He knows that on the i-th day (1 ≤ i ≤ n) he makes ai money. Kefa loves progress, that's why he wants to know the length of the maximum non-decreasing subsegment in sequence ai. Let us remind you that the subsegment of the sequence is its continuous fragment. A subsegment of numbers is called non-decreasing if all numbers in it follow in the non-decreasing order.

Help Kefa cope with this task!

Input

The first line contains integer n (1 ≤ n ≤ 105).

The second line contains n integers a1, a2, ..., an (1 ≤ ai ≤ 109).

Output

Print a single integer — the length of the maximum non-decreasing subsegment of sequence a.

							Sample test(s)

									input
6
2 2 1 3 4 1

									output
3

									input
3
2 2 9

									output
3

Note

In the first test the maximum non-decreasing subsegment is the numbers from the third to the fifth one.

In the second test the maximum non-decreasing subsegment is the numbers from the first to the third one.

题目大意：给出一个序列，求它的最长不降子段的长度。

$O\left(n\right)$扫过去。

Kefa wants to celebrate his first big salary by going to restaurant. However, he needs company.

Kefa has n friends, each friend will agree to go to the restaurant if Kefa asks. Each friend is characterized by the amount of money he has and the friendship factor in respect to Kefa. The parrot doesn't want any friend to feel poor compared to somebody else in the company (Kefa doesn't count). A friend feels poor if in the company there is someone who has at least d units of money more than he does. Also, Kefa wants the total friendship factor of the members of the company to be maximum. Help him invite an optimal company!

Input

The first line of the input contains two space-separated integers, n and d (1 ≤ n ≤ 105, $\text{[math]}$ ) — the number of Kefa's friends and the minimum difference between the amount of money in order to feel poor, respectively.

Next n lines contain the descriptions of Kefa's friends, the (i + 1)-th line contains the description of the i-th friend of type mi, si (0 ≤ mi, si ≤ 109) — the amount of money and the friendship factor, respectively.

Output

Print the maximum total friendship factir that can be reached.

							Sample test(s)

									input
4 5
75 5
0 100
150 20
75 1

									output
100

									input
5 100
0 7
11 32
99 10
46 8
87 54

									output
111

Note

In the first sample test the most profitable strategy is to form a company from only the second friend. At all other variants the total degree of friendship will be worse.

In the second sample test we can take all the friends.

题目大意：有n个朋友，给出每个朋友有的钱和他的友谊因数，要选出若干个朋友举行聚会，要在选出的每个朋友都不感到自己很穷的前提下，所有人的友谊因数之和最大。一个朋友如果发现一同聚会的人中有人的钱比他多至少d个单位就会感到很穷。求最大的友谊因数之和。

将所有朋友按钱的多少排序，两个指针扫过去。

Kefa decided to celebrate his first big salary by going to the restaurant.

He lives by an unusual park. The park is a rooted tree consisting of n vertices with the root at vertex 1. Vertex1 also contains Kefa's house. Unfortunaely for our hero, the park also contains cats. Kefa has already found out what are the vertices with cats in them.

The leaf vertices of the park contain restaurants. Kefa wants to choose a restaurant where he will go, but unfortunately he is very afraid of cats, so there is no way he will go to the restaurant if the path from the restaurant to his house contains more than m consecutive vertices with cats.

Your task is to help Kefa count the number of restaurants where he can go.

Input

The first line contains two integers, n and m (2 ≤ n ≤ 105, 1 ≤ m ≤ n) — the number of vertices of the tree and the maximum number of consecutive vertices with cats that is still ok for Kefa.

The second line contains n integers a1, a2, ..., an, where each ai either equals to 0 (then vertex i has no cat), or equals to 1 (then vertex i has a cat).

Next n - 1 lines contains the edges of the tree in the format "xi yi" (without the quotes) (1 ≤ xi, yi ≤ n, xi ≠ yi), where xi and yi are the vertices of the tree, connected by an edge.

It is guaranteed that the given set of edges specifies a tree.

Output

A single integer — the number of distinct leaves of a tree the path to which from Kefa's home contains at mostm consecutive vertices with cats.

							Sample test(s)

									input
4 1
1 1 0 0
1 2
1 3
1 4

									output
2

									input
7 1
1 0 1 1 0 0 0
1 2
1 3
2 4
2 5
3 6
3 7

									output
2

Note

Let us remind you that a tree is a connected graph on n vertices and n - 1 edge. A rooted tree is a tree with a special vertex called root. In a rooted tree among any two vertices connected by an edge, one vertex is a parent (the one closer to the root), and the other one is a child. A vertex is called a leaf, if it has no children.

Note to the first sample test: $\text{[math]}$ The vertices containing cats are marked red. The restaurants are at vertices 2, 3, 4. Kefa can't go only to the restaurant located at vertex 2.

Note to the second sample test: $\text{[math]}$ The restaurants are located at vertices 4, 5, 6, 7. Kefa can't go to restaurants 6, 7.

题目大意：Kefa住在一个树形的公园里，这棵树的1号节点是它家，叶节点上有餐厅，有些节点上有猫，Kefa非常怕猫，所以求从它家出发经过不超过m个有猫的连续节点能到达的餐厅数量。

DFS一遍就行了。

When Kefa came to the restaurant and sat at a table, the waiter immediately brought him the menu. There were n dishes. Kefa knows that he needs exactly m dishes. But at that, he doesn't want to order the same dish twice to taste as many dishes as possible.

Kefa knows that the i-th dish gives him ai units of satisfaction. But some dishes do not go well together and some dishes go very well together. Kefa set to himself k rules of eating food of the following type — if he eats dish x exactly before dish y (there should be no other dishes between x and y), then his satisfaction level raises by c.

Of course, our parrot wants to get some maximal possible satisfaction from going to the restaurant. Help him in this hard task!

Input

The first line of the input contains three space-separated numbers, n, m and k (1 ≤ m ≤ n ≤ 18,0 ≤ k ≤ n * (n - 1)) — the number of dishes on the menu, the number of portions Kefa needs to eat to get full and the number of eating rules.

The second line contains n space-separated numbers ai, (0 ≤ ai ≤ 109) — the satisfaction he gets from the i-th dish.

Next k lines contain the rules. The i-th rule is described by the three numbers xi, yi and ci (1 ≤ xi, yi ≤ n,0 ≤ ci ≤ 109). That means that if you eat dish xi right before dish yi, then the Kefa's satisfaction increases byci. It is guaranteed that there are no such pairs of indexes i and j (1 ≤ i < j ≤ k), that xi = xj and yi = yj.

Output

In the single line of the output print the maximum satisfaction that Kefa can get from going to the restaurant.

							Sample test(s)

									input
2 2 1
1 1
2 1 1

									output
3

									input
4 3 2
1 2 3 4
2 1 5
3 4 2

									output
12

Note

In the first sample it is best to first eat the second dish, then the first one. Then we get one unit of satisfaction for each dish and plus one more for the rule.

In the second test the fitting sequences of choice are 4 2 1 or 2 1 4. In both cases we get satisfaction 7 for dishes and also, if we fulfill rule 1, we get an additional satisfaction 5.

题目大意：有n种菜，给出每种菜的美味程度，另外有k个规则，每个规则x,y表示如果恰好在吃完x后吃y，可以获得额外的美味程度c。现在一共要吃m道不重复的菜，求最大的美味程度之和。

用$f_{i,j}$表示已经吃过的菜的二进制表示为i，最后吃的菜是j的最大美味程度，简单地DP一下就行了。Cf机器很快，虽然复杂度最大时可以到8千多万，半秒就可以跑过了。

One day Kefa the parrot was walking down the street as he was on the way home from the restaurant when he saw something glittering by the road. As he came nearer he understood that it was a watch. He decided to take it to the pawnbroker to earn some money.

The pawnbroker said that each watch contains a serial number represented by a string of digits from 0 to 9, and the more quality checks this number passes, the higher is the value of the watch. The check is defined by three positive integers l, r and d. The watches pass a check if a substring of the serial number from l to r has period d. Sometimes the pawnbroker gets distracted and Kefa changes in some substring of the serial number all digits to c in order to increase profit from the watch.

The seller has a lot of things to do to begin with and with Kefa messing about, he gave you a task: to write a program that determines the value of the watch.

Let us remind you that number x is called a period of string s (1 ≤ x ≤ |s|), if si = si + x for all i from 1 to|s| - x.

Input

The first line of the input contains three positive integers n, m and k (1 ≤ n ≤ 105, 1 ≤ m + k ≤ 105) — the length of the serial number, the number of change made by Kefa and the number of quality checks.

The second line contains a serial number consisting of n digits.

Then m + k lines follow, containing either checks or changes.

The changes are given as 1 l r с (1 ≤ l ≤ r ≤ n, 0 ≤ c ≤ 9). That means that Kefa changed all the digits from the l-th to the r-th to be c.

The checks are given as 2 l r d (1 ≤ l ≤ r ≤ n, 1 ≤ d ≤ r - l + 1).

Output

For each check on a single line print "YES" if the watch passed it, otherwise print "NO".

							Sample test(s)

									input
3 1 2
112
2 2 3 1
1 1 3 8
2 1 2 1

									output
NO
YES

									input
6 2 3
334934
2 2 5 2
1 4 4 3
2 1 6 3
1 2 3 8
2 3 6 1

									output
NO
YES
NO

Note

In the first sample test two checks will be made. In the first one substring "12" is checked on whether or not it has period 1, so the answer is "NO". In the second one substring "88", is checked on whether or not it has period 1, and it has this period, so the answer is "YES".

In the second statement test three checks will be made. The first check processes substring "3493", which doesn't have period 2. Before the second check the string looks as "334334", so the answer to it is "YES". And finally, the third check processes substring "8334", which does not have period 1.

题目大意：给出一个数字串，有两种操作，第一种是将区间$\left[l,r\right]$全都改成数字c，第二种是问区间$\left[l,r\right]$是否可以形成周期为d的循环。

第二种操作等价于问区间$\left[l+d,r\right]$和区间$\left[l,r-d\right]$中的数字是否一样。用线段树维护数字串的哈希，注意哈希的模数要多取几个防止冲突。

A-E代码在此。

Category: 题解 | Tags: DP 哈希位运算树线段树 Codeforces 暴力 | Read Count: 1496

Stalker's Blog

I am here in the shadows.