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.
For each test case, the first line contains three integers corresponding to n (2≤n≤5×10
The sum of n for all cases would not be larger than 5×10
6
.
Output
The output contains exactly T lines.
For each test case, you should output the maximum value of at2i+btj.
For each test case, you should output the maximum value of at
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分开考虑；
代码：
#include<stdio.h>
#include<string.h>
#include<math.h>
#define MAX(x,y)(x>y?x:y)
#define F for(int i=0;i<n;i++)
const int MAXN=;
const int INF=0x3f3f3f3f;
int m[MAXN],vis[MAXN];
int main(){
int T;
int n,a,b,flot=;
scanf("%d",&T);
while(T--){
memset(vis,,sizeof(vis));
scanf("%d%d%d",&n,&a,&b);
long long sum=,x,k;//xΪlong long
F scanf("%d",m+i);
if(a>){
x=-INF;
F if(x<fabs(m[i]))x=fabs(m[i]),k=i;
vis[k]=;
sum+=a*x*x;
}
else if(a<){
x=INF;
F if(x>fabs(m[i]))x=fabs(m[i]),k=i;
vis[k]=;
sum+=a*x*x;
}
if(b>){
x=-INF;
F if(x<m[i]&&!vis[i])x=m[i],k=i;
vis[k]=;
sum+=b*x;
}
else if(b<){
x=INF;
F if(x>m[i]&&!vis[i])x=m[i],k=i;
vis[k]=;
sum+=b*x;
}
printf("Case #%d: %lld\n",++flot,sum);
}
return ;
}
/*#include<stdio.h>
#include<algorithm>
#include<math.h>
#define MAX(x,y)(x>y?x:y)
#define js(x,y)(a*x*x+b*y)
using namespace std;
const int MAXN=5000010;
const int INF=0x3f3f3f3f;
int m[MAXN],ml[MAXN];
int main(){
int T,a,b,n,t[5],ans;
scanf("%d",&T);
for(int i=1;i<=T;i++){
scanf("%d%d%d",&n,&a,&b);
for(int j=0;j<n;j++)scanf("%d",m+j),ml[j]=fabs(m[j]);
t[0]=*max_element(m,m+n);t[1]=*min_element(m,m+n);
*max_element(m,m+n)=-INF;
t[2]=*max_element(m,m+n);
*min_element(m,m+n)=INF;
*min_element(m,m+n)=INF;
t[3]=*min_element(m,m+n);
ans=-INF;
printf("%d %d %d %d\n",t[0],t[1],t[2],t[3]);
if(a>=0&&b>=0){
if(fabs(t[1])>=fabs(t[0]))
ans=js(t[1],t[0]);
else
ans=MAX(js(t[0],t[2]),js(t[2],t[0]));
}
else if(a>=0&&b<0){
if(fabs(t[0])>=fabs(t[1]))
ans=js(t[0],t[1]);
else
ans=MAX(js(t[1],t[3]),js(t[3],t[1]));
}
else{
int x=*min_element(ml,ml+n); }
printf("Case #%d: %d\n",i,ans);
}
return 0;
}*/