Largest Point

**Time Limit: 1500/1000 MS (Java/Others)    Memory Limit: 65535/32768 K (Java/Others)
Total Submission(s): 969    Accepted Submission(s): 384
**

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

Source

2015 ACM/ICPC Asia Regional Shenyang Online

题意：在一个数组里找两个下标不一样的数，使at2i+btj最大，下标不一样，数值可能一样

#include
#include
#include
#include
#include

using namespace std;

const int maxn = *1e6+;
#define INF 0x3f3f3f3f

struct node
{
int x, id;
}P[maxn];

int cmp(node a, node b)
{
return abs(a.x) < abs(b.x);
}

int cmp1(node a, node b)
{
return a.x < b.x;
}

int main()
{
int t, n, a, b, l = ;
int A1, a1, ma, B1, b1, mb;
scanf("%d", &t);
long long sum, ans;
while(t--)
{
scanf("%d%d%d", &n, &a, &b);
for(int i = ; i < n; i++) { scanf("%d", &P[i].x); P[i].id = i; } A1 = a1 = ma = B1 = b1 = mb = ; sort(P, P+n, cmp); if(a >= )
A1 = P[n-].x, a1 = P[n-].id, ma = P[n-].x;
else
A1 = P[].x, a1 = P[].id, ma = P[].x;
sort(P, P+n, cmp1);
if(b >= )
B1 = P[n-].x, b1 = P[n-].id, mb = P[n-].x;
else
B1 = P[].x, b1 = P[].id, mb = P[].x;
if(a1 != b1)
{
sum = (long long)a * A1 *A1;
sum += (long long)b * B1;
}

     else  
     {  
         sum = (long long)a \* A1\*A1;  
         sum += (long long)b\*mb;   // 为什么非得这么加，这么强制转换，orWA  
         ans = (long long)a\*ma\*ma;  
         ans += (long long)b\*B1;  
         sum = sum > ans ? sum : ans;  
     }  
     printf("Case #%d: %I64d\\n",l++,  sum);  
 }  
 return ;  

}