#P4087. [Sdoi2015]模拟电路
[Sdoi2015]模拟电路
[SDOI2015] 模拟电路
题目描述
一块芯片有 个插槽。每个插槽最多可放一个稳压组件。部分插槽不可用或已装有组件,你只能在开放且未被占用的插槽中安装新组件。
设安装后的组件总数为 ,第 行、第 列中的组件数分别是 。总数、行数和列数均计入原有的组件。芯片须满足以下条件:
- 对于第 行,给定 个列编号 。若该列表非空,则 ;列表为空时,第 行没有这一项限制。
- 对于每个 ,给定比例 ()。第 行的组件数不得超过 ,第 列的组件数不得超过 。
求最多可安装多少个新组件。
输入格式
第一行一个正整数 (),表示芯片的边长。接下来 行,每行 个字符,分别用 .、/、C 表示开放、不可用和已被组件占据的插槽。
接下来 行描述行约束。第 行先给出非负整数 ,再给出 个互不相同的列编号,均在 到 之间。
接下来一行给出 ,最后一行给出 。每个比例小数点后至多三位。
输出格式
如果可以达到要求,输出最多可新装的组件数;否则输出 impossible。
数据范围
- 对于 的数据,。
- 存在 的数据,所有 ;其中占全部数据 的部分没有已被占据的插槽。
- 存在 的数据,所有 ,且 。
样例 #1
样例输入 #1
5
CC/..
././/
..C.C
/.C..
/./C/
1 1
1 2
1 3
1 4
1 5
0.3 0.3 0.3 0.3 0.3
0.3 0.3 0.3 0.3 0.3
样例输出 #1
7
样例 #2
样例输入 #2
5
CC/..
././/
..C.C
/.C..
/./C/
1 1
1 2
1 3
1 4
1 5
0.2 0.2 0.2 0.2 0.2
0.2 0.2 0.2 0.2 0.2
样例输出 #2
impossible
样例说明
样例 1 每行、每列至多容纳总数的 。以下是安装 个新组件的一种方案,W 表示新组件:
CC/W.
W/W//
W.C.C
/.CWW
/W/C/
