No tags yet

No tag edit access

The problem statement has recently been changed. View the changes.

×
time limit per test: 0.25 sec.

memory limit per test: 65536 KB

memory limit per test: 65536 KB

input: standard

output: 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 left-aligned rows. The i-th 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.

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.

The first line of the input file contains two integer numbers n and k (1 <= n, k <= 250). The second line contains n space-delimited numbers (b_1, b_2, ..., b_n) (1 <= b_i <= 250, i=1..n).

Write to the output single integer -- number of different peaceful rooks dispositions on the given board.

Input

Test #1

2 2

2 3

Test #2

3 3

2 1 2

2 2

2 3

Test #2

3 3

2 1 2

Output

Test #1

4

Test #2

0

4

Test #2

0

Author: | Michael R. Mirzayanov |

Resource: | ACM ICPC 2004-2005, NEERC, Southern Subregional Contest |

Date: | Saratov, October 7, 2004 |

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Mar/02/2021 08:42:31 (f1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|