Largest Point
Time Limit: 1500/1000 MS (Java/Others) Memory Limit: 65535/32768 K (Java/Others)
Total Submission(s): 973 Accepted Submission(s): 386
Problem Description
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
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
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 <iostream>
#include <stdio.h>
#include <string.h>
#include <cmath>
#include <algorithm>
#include <map>
#include <queue>
using namespace std;
const int maxn=5000000+10;
const int inf=(1<<30);
struct Node
{
int i;
__int64 ans;
}p[maxn],q[maxn];
bool cmp(Node a,Node b)
{
return a.ans>b.ans;
}
int main()
{
int t,cnt=1;
scanf("%d",&t);
while(t--)
{
__int64 n,a,b,c;
scanf("%I64d%I64d%I64d",&n,&a,&b);
for(int i=0;i<n;i++)
{
scanf("%I64d",&c);
p[i].ans=a*c*c; //注意溢出
q[i].ans=b*c;
p[i].i=q[i].i=i;
}
sort(p,p+n,cmp);
sort(q,q+n,cmp);
printf("Case #%d: ",cnt++);
if(p[0].i==q[0].i)
{
__int64 res=max(p[0].ans+q[1].ans,p[1].ans+q[0].ans);
printf("%I64d\n",res);
}
else
printf("%I64d\n",p[0].ans+q[0].ans);
}
return 0;
}