TopCoder

User's AC Ratio

50.0% (1/2)

Submission's AC Ratio

50.0% (1/2)

Tags

Description

在很遠很遠的地方,有一個住著$N$個人的城市。在這個城市裡的每個人都十分貪吃,只要拿到他們喜歡的食物,就有可能變得快樂。不過,食物是會吃膩的,所以每個人不管拿到幾份同種的食物,效果相當於只拿一份該種食物。
身為市長的你,現在手邊有$M$種食物,第$i$種食物有$a_i$份。已知第$j$個人吃到第$i$種食物時,有$P(i,\ j)\%$的機率變得快樂。請問在最好的分配食物的策略下,快樂人數的期望值為何?

Input Format

輸入第一行含有兩個整數$N,\ M$,代表市民數與食物種類數。
第二行有$M$個整數$a_i\ (0\le a_i \le N)$,表示第$i$種食物的份數。
接著有$M$行,每行有$N$個正整數。
第$i$行第$j$列的數字為$P(i.\ j)\ (0\leq P(i,\ j)\leq 100)$,表示第$j$個人吃到第$i$種食物時變快樂的機率百分比。

Testdata Score Constraint
Subtask 1 0~4 5 $N\leq10,\ M = 2$
Subtask 2 5~8 15 $N\leq 10,\ M\leq 4$
Subtask 3 9~19 20 $N\le 500,\ M\leq4$
Subtask 4 20~29 25 $N\le 10000,\ M\leq3$
Subtask 5 30~39 35 $N\le 500000,\ M\leq2$

Output Format

若快樂人數的期望值為$P$,可以證明$P\times 100^ M$為整數。請輸出這個整數。

Sample Input

Test Case #1:
3 2
2 2
100 0 50
0 100 50

Test Case #2:
6 3
1 4 2
91 22 53 93 54 38
15 24 51 88 13 49
25 4 47 55 100 79

Sample Output

Test Case #1:
27500

Test Case #2:
4432900

Hints

即使兩種食物讓同一個人變快樂
還是只有那一個人快樂唷

Problem Source

Problem Set and Description by $e ^ { r ^ { d } } 1 $

Subtasks

For Testdata: 0 ~ 4, Score: 5
For Testdata: 5 ~ 8, Score: 15
For Testdata: 9 ~ 19, Score: 20
For Testdata: 20 ~ 29, Score: 25
For Testdata: 30 ~ 39, Score: 35
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 5000 32768 65536
1 5000 32768 65536
2 5000 32768 65536
3 5000 32768 65536
4 5000 32768 65536
5 5000 32768 65536
6 5000 32768 65536
7 5000 32768 65536
8 5000 32768 65536
9 5000 32768 65536
10 5000 32768 65536
11 5000 32768 65536
12 5000 32768 65536
13 5000 32768 65536
14 5000 32768 65536
15 5000 32768 65536
16 5000 32768 65536
17 5000 32768 65536
18 5000 32768 65536
19 5000 32768 65536
20 5000 32768 65536
21 5000 32768 65536
22 5000 32768 65536
23 5000 32768 65536
24 5000 32768 65536
25 5000 32768 65536
26 5000 32768 65536
27 5000 32768 65536
28 5000 32768 65536
29 5000 32768 65536
30 5000 32768 65536
31 5000 32768 65536
32 5000 32768 65536
33 5000 32768 65536
34 5000 32768 65536
35 5000 32768 65536
36 5000 32768 65536
37 5000 32768 65536
38 5000 32768 65536
39 5000 32768 65536