#include<bits/stdc++.h>
#define ll long long
#define all(x) x.begin(),x.end()
#define maxn 100005
#define inf 1000000000000000000
#define pi pair<int,int>
#define pl pair<ll,int>
#define fi first
#define se second
using namespace std;
struct point
{
ll x,y;
int id;
point(ll _x=0,ll _y=0,int _id=0)
{
x=_x;
y=_y;
id=_id;
}
};
point operator + (point A,point B)
{
return point(A.x+B.x,A.y+B.y);
}
point operator - (point A,point B)
{
return point(A.x-B.x,A.y-B.y);
}
ll dot(point A,point B)
{
return A.x*B.x+A.y*B.y;
}
ll cross(point A,point B)
{
return A.x*B.y-A.y*B.x;
}
struct
{
vector<point>tt;
vector<point>convex1;
vector<point>convex2;
vector<point>buildConvex(vector<point>cur)
{
sort(all(cur),[](point A,point B)
{
if(A.x!=B.x)return A.x<B.x;
return A.y>B.y;
});
vector<point>tmp;
tmp.push_back(cur[0]);
for(int i=1; i<(int)cur.size(); i++)
{
if(cur[i-1].x!=cur[i].x)
{
tmp.push_back(cur[i]);
}
}
vector<point>convex;
if(tmp.size()>=1)convex.push_back(tmp[0]);
if(tmp.size()>=2)convex.push_back(tmp[1]);
if(tmp.size()>=3)
{
for(int i=2; i<tmp.size(); i++)
{
while(convex.size()>=2&&
cross(tmp[i]-convex[convex.size()-1],convex[convex.size()-2]-convex[convex.size()-1])>=0)
{
convex.pop_back();
}
convex.push_back(tmp[i]);
}
}
return convex;
}
int nho[maxn];
void init()
{
convex1=buildConvex(tt);
for(auto[x,y,id]:convex1)nho[id]=1;
convex2.clear();
for(auto[x,y,id]:tt)
{
if(!nho[id])
{
convex2.push_back(point(x,y,id));
}
}
convex2=buildConvex(convex2);
}
ll f1(int A,int B,int id)
{
if(id==-1)return 0;
return A*convex1[id].x+B*convex1[id].y;
}
pi Find1(int A,int B)
{
int lo=0;
int hi=convex1.size()-1;
/*
for(int t=0; t<=100; t++)
{
int x1=lo+(hi-lo)/3;
int x2=hi-(hi-lo)/3;
if(hi-lo<=5)break;
if(f(A,B,x1)<f(A,B,x2))
{
lo=x1;
}
else if(f(A,B,x1)>f(A,B,x2))
{
hi=x2;
}
else
{
lo=x1;
hi=x2;
}
}
*/
ll val1=0;int p1=-1;
ll val2=0;int p2=-1;
for(int i=0; i<=(int)convex1.size()-1; i++)
{
ll cur=f1(A,B,i);
if(val1<=cur)
{
val2=val1;
p2=p1;
val1=cur;
p1=i;
}
else if(val2<=cur)
{
val2=cur;
p2=i;
}
}
return {p1,p2};
}
ll f2(int A,int B,int id)
{
if(id==-1)return 0;
return A*convex2[id].x+B*convex2[id].y;
}
int Find2(int A,int B)
{
int lo=0;
int hi=convex2.size()-1;
/*
for(int t=0; t<=100; t++)
{
int x1=lo+(hi-lo)/3;
int x2=hi-(hi-lo)/3;
if(hi-lo<=5)break;
if(f(A,B,x1)<f(A,B,x2))
{
lo=x1;
}
else if(f(A,B,x1)>f(A,B,x2))
{
hi=x2;
}
else
{
lo=x1;
hi=x2;
}
}
*/
ll val1=0;int p1=-1;
for(int i=0; i<=(int)convex2.size()-1; i++)
{
ll cur=f2(A,B,i);
if(val1<=cur)
{
val1=cur;
p1=i;
}
}
return p1;
}
void Add_Pair(int X,int Y,int id)
{
tt.push_back(point(X,Y,id));
}
}AP,DP;
void Init(vector<int>A,vector<int>D,vector<int>P)
{
int n=A.size();
for(int i=0;i<n;i++)
{
AP.Add_Pair(A[i],P[i],i);
DP.Add_Pair(D[i],P[i],i);
}
AP.init();
DP.init();
}
ll BestSquad(int X, int Y)
{
pi CandAp=AP.Find1(X,Y);
int CandAp2=AP.Find2(X,Y);
pi CandDp=DP.Find1(X,Y);
int CandDp2=DP.Find2(X,Y);
//cout<<AP.tt[CandAp.fi].id<<' '<<AP.tt[CandAp.se].id<<'\n';
//cout<<DP.tt[CandDp.fi].id<<' '<<DP.tt[CandDp.se].id<<'\n';
ll ans=0;
if(AP.tt[CandAp.fi].id!=DP.tt[CandDp.fi].id)
{
ans=AP.f1(X,Y,CandAp.fi)+DP.f1(X,Y,CandDp.fi);
}
else
{
ans=max(ans,AP.f1(X,Y,CandAp.fi)+DP.f1(X,Y,CandDp.se));
ans=max(ans,AP.f1(X,Y,CandAp.fi)+DP.f2(X,Y,CandDp2));
ans=max(ans,DP.f1(X,Y,CandDp.fi)+AP.f1(X,Y,CandAp.se));
ans=max(ans,DP.f1(X,Y,CandDp.fi)+AP.f2(X,Y,CandAp2));
}
return ans;
}
/*
int main()
{
Init({3, 3, 5, 2, 1}, {2, 1, 1, 1, 4}, {5, 4, 3, 1, 2});
cout << BestSquad(2, 5) << "\n";
//Init({3, 2, 2, 4}, {1, 3, 1, 4}, {4, 3, 6, 1});
//cout << BestSquad(1, 3) << '\n';
return 0;
}
*/
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |