Largest Point

Time Limit: 1500/1000 MS (Java/Others) Memory Limit: 65535/32768 K (Java/Others)
Total Submission(s): 637 Accepted Submission(s): 266

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

23 2 11 2 35 -1 0-3 -3 0 3 3

Sample Output

Case #1: 20Case #2: 0

Source

/*小技巧：分析：对于数组中的每一个t，我们用两个数组A和B分别纪录a*ti^2和b*ti，然后对这两个数组排序，如果两个数组最大值的下标不同，那么相加就是最大值了，如果相同，那么就拿A数组的次大值加上B数组的最大值，和A数组的最大值加上B数字的次大值这两个值相比较，较大的即为最终的最大值。*///改进不用快排 #include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           using namespace std;const int N=5e+6+10;struct Node{ long long v; int id;}num1,num2,num11,num22;int main(){ int t,n,i; long long a,b,z; scanf("%d",&t); int now=1; while(t--){ long long re=0; num1.v=-(5e+18); num11.v=-(5e+18); num2.v=-(5e+18); num22.v=-(5e+18); num1.id=0; num11.id=0; num2.id=0; num22.id=0; scanf("%d%lld%lld",&n,&a,&b); for(i=0;i
           
            num1.v){ num11.v=num1.v; num11.id=num1.id; num1.v=a*z*z; num1.id=i; } else if(a*z*z>num11.v){ num11.v=a*z*z; num11.id=i; } if(b*z>num2.v){ num22.v=num2.v; num22.id=num2.id; num2.v=b*z; num2.id=i; } else if(b*z>num22.v){ num22.v=b*z; num22.id=i; } } if(num1.id!=num2.id) re=num1.v+num2.v; else re=max(num1.v+num22.v,num11.v+num2.v); printf("Case #%d: %lld\n",now++,re);} return 0;}/*超时 长得丑....... #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 
                  #include 
                  
                   using namespace std;const int N=5*1e6+10;struct Node{ long long v; int id; bool operator <(const Node &b) const { if(v==b.v) return id
                   
                    #include 
                    
                     #include 
                     
                      using namespace std;const int maxn=5e6+10;int n,a,b;struct node{ int id; long long x; bool operator <(const node &a) const { return x
                      
                       y?x:y;}int main(){ int t,T=1; scanf("%d",&t); while(t--) { scanf("%d%d%d",&n,&a,&b); for(int i=0;i