bzoj#P2139. road

road

题目描述

很久很久以前,中原地区分成了 NN 个国家,编号为 1N1\sim N,任意两个国家都可互达。每个国家有一个攻击值 AiA_i 和防御值 BiB_i 。定义一个人从 ii 国去 jj 国的危险值为:假如 Ai>BjA_i>B_j ,则危险值为 Ai2Bj2A_i^2-B_j^2,否则危险值为 00 。现在,Nan 从国家 11 出发,经过每一个国家有且仅有一次,最后回到国家 11 ,要求找出一种方案,使得其中危险值的最大值最小。

输入格式

第一行正整数 NN ,表示有 NN 个国家;

第二行正整数 A1,A2,x,y,zA_1,A_2,x,y,z,有等式 Ai=(x×Ai1+y×Ai2+z)mod32767A_i=(x\times A_{i-1}+y\times A_{i-2}+z)\mod 32767

第三行正整数 B1,B2,x,y,zB_1,B_2,x,y,z,有等式 Bi=(x×Bi1+y×Bi2+z)mod32767B_i=(x\times B_{i-1}+y\times B_{i-2}+z)\mod 32767

输出格式

输出一个数,表示危险值的最大值最小是多少。

5
2 4 1231 4432 123
123 45 3245 555 6676
9171832

数据规模与约定

对于 100%100\% 的数据, 1N1061\le N\le 10^6

样例说明

A 数组为 2,4,13911,5151,30312,4,13911,5151,3031 。 B 数据为 123,45,24364,26060,21765123,45,24364,26060,21765。 其中一种最优方案为 1243511- 2- 4- 3- 5-1,危险值分别为 0,0,0,0,91718320,0,0,0,9171832