「BZOJ3158」千钧一发

2014年12月15日4,3961

Description

Input

第一行一个正整数N。

第二行共包括N个正整数,第 个正整数表示Ai。

第三行共包括N个正整数,第 个正整数表示Bi。

Output

共一行,包括一个正整数,表示在合法的选择条件下,可以获得的能量值总和的最大值。

Sample Input

4
3 4 5 12
9 8 30 9

Sample Output

39

HINT

1<=N<=1000,1<=Ai,Bi<=10^6

题解

可以证明,任意两个偶数满足2

两个奇数满足1

(2a+1)^2+(2b+1)^2=2(2a^2+2b^2+2a+2b+1)

一定不是完全平方数

所以可以用最小割解决此题

 

avatar
1 Comment threads
0 Thread replies
0 Followers
 
Most reacted comment
Hottest comment thread
1 Comment authors
黄学长的粉丝 Recent comment authors
  Subscribe  
提醒
黄学长的粉丝
黄学长的粉丝

第一眼最大团给跪了.