269. Rooks
time limit per test: 0.25
sec.
memory limit per test: 65536
KB
input: standard
output: standard
Let's define a board as a finite subset of infinite chessboard cells. The (b_1, b_2, ..., b_n) board is the board with n leftaligned rows. The ith line consists of b_i sequential cells. For example, (1, 4, 3, 5) board looks as follows:
The rook can be placed on any cell of the board. The rooks disposition is called peaceful if and only if no two rooks stay on the same vertical or horizontal line (no matter if all cells between them belong to the (b_1, b_2, ..., b_n) board or not).
Your task is to find a number of peaceful dispositions of k rooks for the (b_1, b_2, ..., b_n) board.
Input
The first line of the input file contains two integer numbers n and k (1 <= n, k <= 250). The second line contains n spacedelimited numbers (b_1, b_2, ..., b_n) (1 <= b_i <= 250, i=1..n).
Output
Write to the output single integer  number of different peaceful rooks dispositions on the given board.
Sample test(s)
Input
Test #1
2 2
2 3
Test #2
3 3
2 1 2
Output
Test #1
4
Test #2
0
Author:  Michael R. Mirzayanov

Resource:  ACM ICPC 20042005, NEERC, Southern Subregional Contest

Date:  Saratov, October 7, 2004

Server time: 20160530 15:33:00  Online Contester Team © 2002  2016. All rights reserved. 

