#BZOJ3753. Wall
-
ID: 2311
Type: RemoteJudge
1000ms
256MiB
Tried: 0
Accepted: 0
Difficulty: (None)
Uploaded By:
root
Wall
No submission language available for this problem.
题目描述
众所周知，GFW的出现促进了社会的和谐。Wayne于是想研究一下GFW。
Wayne喜欢网格，所以他把一些网站排成了N_ M的网格，每个格子代表一个网站。每个网
站有一个评分，当然评分可正可负。现在Wayne想用一堵“墙”围住一些网站，使得评分和最大。
所谓“墙”，就是一个由网格的边组成的简单多边形，不能自交，也不能有空洞。
过了一会儿Wayne发现这个模型太一般了。出于一些原因，有些网站必须在“墙”外，我们称之
为“坏网站”；而有些网站必须在“墙”内，我们称之为“好网站”。当然了，“坏网站”的评分不一定
低，“好网站”的评分不一定高。Wayne又想知道，这种情况下，能够得到的最大评分和。注意，并
不总是存在合法的方案，所以当无法实现时，输出“Can not establish GFW.”。
输入格式
第一行两个正整数N和M。
接下来N行，每行M个用空格隔开的整数，表示网站的权值。
最后N行，每行M个用空格隔开的整数，1 表示坏网站，2 表示好网站，0 表示其他网站。
输出格式
输出两行，第一行一个整数表示一堵“墙”能围住的最大评分和，第二行表示有限制时的答案。
3 3
2 -1 2
-3 100 -3
-3 20 -3
2 0 2
0 1 0
0 0 0
123
17
数据范围与约定
对于 100% 的数据，N<=10，M<=10，权值的绝对值不超过 10^6 ，且至少一个权值非负，至少一个好网站。