Power of Rinnegan
All submissions for this problem are available.Sasuke has awakened Rinnegan in his left eye. Now he has many supernatural abilities. One of the many special abilities of Sasuke's Rinnegan is to shift spaces within a certain distance from himself. He can also carry other persons with him while shifting, but there is a limit to the number of persons he can carry at a time. He is going from a point 1 to a point N in space following a certain path that is pre decided. There are certain points where he stops during his journey as he can shift upto a certain distance from himself. These points are also pre decided. There are many people waiting at each of these points to be carried using his Rinnegan to some point ahead in his path. The people whom he carries give him some of their energy so that he can work continuously. The transfer of energy takes place as per the following rule
There is an array ARR of distinct integers following one based indexing. A function f(i) is defined on this array as the number of permutations of (ARR, ARR .. , ARR[i]) except the ones in which the condition (ARR[a] < ARR[b] < ARR[c]) is satisfied for any a,b,c such that 1 ≤ a < b < c ≤ i.
Another function F(i) = f(i) modulo 1009
The energy an individual travelling from a point A to a point B transfers to Sasuke is equal to [F(B) - F(A)] modulo 1009
If the number of points Sasuke stops is N (including 1 and N), then his path is 1 -> 2 -> 3 -> .. -> N. This path is fixed.
Given the number of points Sasuke stops N, the number of persons who are waiting at point x and want to go to point y [1 ≤ x < y ≤ N] Cxy and the number of persons he can carry with him at a time P, find the maximum amount of energy that he can gain during the journey. You don't have to take modulo while calculating energy here.
Note : Sasuke will not travel backward. i.e. Once he reaches a point i, he will not go to any point less than i. The only point that he moves next is i+1(if i is not equal to N) and not any other point.
The first line contains two integers, the number of points Sasuke stops N and the number of persons he can carry at a time P.
The next line contains N integers representing the array ARR.
The next N-1 lines contains the description of number of people waiting at each point.
The ith line contains N-i integers, one integer for each point where Sasuke stops after i.
The jth integer in the ith line is the number of persons who are waiting at point i and want to go to point k Cik where k = i+j
More formally for every i, k = i + 1 to N
Output a single integer, the maximum energy that Sasuke can gain during the journey.
- 1 ≤ N ≤ 50
- 1 ≤ P ≤ 100
- 1 ≤ ARR[i] ≤ 10^5
- 1 ≤ Cik ≤ 100 for all i, k such that 1 ≤ i < k ≤ N
1 2 3
In first sample
The path is 1 -> 2 -> 3
The number of persons who have to go from 1->2 = 1
The number of persons who have to go from 1->3 = 1
The number of persons who have to go from 2->3 = 1
F(1) = 1
F(2) = 2
F(3) = 5 (every permutation except [1,2,3])
The energy that a person travelling from 1->2 can transfer = 1
The energy that a person travelling from 1->3 can transfer = 4
The energy that a person travelling from 2->3 can transfer = 3
He can carry both the persons waiting at 1 till 2. One of them had to tavell till 2 so he gets off. The person waiting at 2 gets on with Sasuke so now he again has 2 persons to carry. Both of them have to go till 3.
So the total gain in energy = 1*1 + 1*4 + 1*3 = 8
|Tags||aaijmrt, insomnia, min-cost-flow, mnnit, number-theory|
|Time Limit:||2 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA|
Fetching successful submissions