Largest Point

Time Limit: 1500/1000 MS (Java/Others) Memory Limit: 65535/32768 K (Java/Others)

Total Submission(s): 536 Accepted Submission(s): 230

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 n integers 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

题解：

ax2和bx分开考虑；

代码：

1 #include
       
         2 #include
        
          3 #include
         
           4 #define MAX(x,y)(x>y?x:y) 5 #define F for(int i=0;i
          
           0){19             x=-INF;20             F if(x
           
            fabs(m[i]))x=fabs(m[i]),k=i;27                 vis[k]=1;28             sum+=a*x*x;29         }30         if(b>0){31              x=-INF;32             F if(x
            
             m[i]&&!vis[i])x=m[i],k=i;39 vis[k]=1;40 sum+=b*x;41 }42 printf("Case #%d: %lld\n",++flot,sum);43 }44 return 0;45 }46 /*#include
             
              47 #include
              
               48 #include
               
                49 #define MAX(x,y)(x>y?x:y)50 #define js(x,y)(a*x*x+b*y)51 using namespace std;52 const int MAXN=5000010;53 const int INF=0x3f3f3f3f;54 int m[MAXN],ml[MAXN];55 int main(){56 int T,a,b,n,t[5],ans;57 scanf("%d",&T);58 for(int i=1;i<=T;i++){59 scanf("%d%d%d",&n,&a,&b);60 for(int j=0;j
                
                 =0&&b>=0){70 if(fabs(t[1])>=fabs(t[0]))71 ans=js(t[1],t[0]);72 else73 ans=MAX(js(t[0],t[2]),js(t[2],t[0]));74 }75 else if(a>=0&&b<0){76 if(fabs(t[0])>=fabs(t[1]))77 ans=js(t[0],t[1]);78 else79 ans=MAX(js(t[1],t[3]),js(t[3],t[1]));80 }81 else{82 int x=*min_element(ml,ml+n);83 84 }85 printf("Case #%d: %d\n",i,ans);86 }87 return 0;88 }*/