Problem Description
Given the sequence A with n integers t1,t2,⋯,tn. Given the integral coefficients a and b. The fact that select two elements ti and tj of A and i≠j to maximize the value of at2i+btj, becomes the largest point.
Input
An positive integer T, indicating there are T test cases.For each test case, the first line contains three integers corresponding to n (2≤n≤5×106), a (0≤|a|≤106) and b (0≤|b|≤106). The second line contains nintegers t1,t2,⋯,tn where 0≤|ti|≤106 for 1≤i≤n.The sum of n for all cases would not be larger than 5×106.
Output
The output contains exactly T lines.For each test case, you should output the maximum value of at2i+btj.
Sample Input
2
3 2 1
1 2 3
5 -1 0
-3 -3 0 3 3
Sample Output
Case #1: 20
Case #2: 0
#include#include #include #include #include #include #include using namespace std;const int oo = 1e9;const int N = 5*1e6+8;const int M = 6000;typedef long long LL;int ac[N], n;LL ans;struct da{ int num, id;} as[N];int cmp1(da a, da b){ return a.num < b.num;}int cmp2(da a, da b){ return abs(a.num) < abs(b.num);}int main(){ int i, T, a, b, A1, A2, B1, B2, ma, mb, xx=1; LL sum; scanf("%d", &T); while(T--) { scanf("%d %d %d", &n, &a, &b); for(i = 0; i < n; i++) { scanf("%d", &as[i].num); as[i].id = i; } A1 = A2 = B1 = B2 = 0; sort(as, as+n, cmp2); if(a >= 0) A1 = as[n-1].num, A2 = as[n-1].id, ma = as[n-2].num; ///A1 A2保存最大的绝对值以及下标 ma次大绝对值 else A1 = as[0].num, A2 = as[0].id, ma = as[1].num;/// A1 A2 保存最小绝对值及下标 ma次小绝对值 sort(as, as+n, cmp1); if(b >= 0) B1 = as[n-1].num, B2 = as[n-1].id, mb = as[n-2].num;///B1 B2最大的数及下标 mb次大的数 else B1 = as[0].num, B2 = as[0].id, mb = as[1].num;///B1 B2 最小的数及下标 mb 次小的数 if(A2 != B2)///这2个数不是同一个数 { ans = (LL)a*A1*A1; ans += (LL)b*B1; } else { ans = (LL)a*A1*A1; ans += (LL)b*mb; sum = (LL)a*ma*ma; sum += (LL)b*B1; ans = max(ans, sum); } printf("Case #%d: %I64d\n", xx++, ans); } return 0;}