罪犯问题B

成绩 0 开启时间 2013年02月21日 星期四 23:02
折扣 0.8 折扣时间 2013年02月28日 星期四 23:02
允许迟交 是 关闭时间 2013年02月28日 星期四 23:02
输入文件 criminalb.in 输出文件 criminalb.out

一天，警官抓获了N个嫌犯，M个居民站了出来指证他们，每人说了一句话，形式有两种，“***是罪犯”，“***不是罪犯”。已经知道居民还是比较可信的，说谎的人数不会超过K人。且根据每个嫌犯所被怀疑犯的罪不同，每个嫌犯的邪恶程度也不同，用一个正整数表示，该整数越大表明该人如果是罪犯的话他越邪恶，若某人不是罪犯，当然他就一点不邪恶，邪恶程度为0。现在希望你能写个程序判断出罪犯总邪恶程度最大为多少，最小为多少。

【输入格式】

 第一行，两个整数N，M，K含义如题目描述所示。

第二行，N个整数，第i个整数表示编号i的嫌犯被怀疑罪行的邪恶程度。

第3—M+2行，第i+2行有一个整数X，若X大于零，表示有个居民说“X号是罪犯”；若X小于零，表示有个居民说“-X号不是罪犯”。

【输出格式】

共有两行，第一行罪犯总邪恶程度最大为多少，第二行输出总邪恶程度最小为多少。

【样例输入】

2 7 3

2 3

1

2

1

-1

-2

1

-1

【样例输出】

5

2

 

一号是罪犯，二号也是的时候，邪恶程度最大，为5，一号是罪犯，而二号不是的时候，邪恶程度最小，为2。而两人都不是罪犯的时候说谎人数为4，不可能出现这种情况。

 

 

对于30%的数据，N<=10,M<=500;

对于80%的数据，M<=5000;

对于100%的数据，N<=1000,M<=50000;

数据保证有解。

 

 

by kily