Submission #1172833

#TimeUsernameProblemLanguageResultExecution timeMemory
1172833abcdxyz123Organizing the Best Squad (FXCUP4_squad)C++17
0 / 100
0 ms392 KiB
#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; point(ll _x=0,ll _y=0) { x=_x; y=_y; } }; 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; void build() { sort(all(tt),[](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(tt[0]); for(int i=1; i<(int)tt.size(); i++) { if(tt[i-1].x!=tt[i].x) { tmp.push_back(tt[i]); } } if((int)tmp.size()==1) { tmp.clear(); tmp.push_back(tt[0]); tmp.push_back(tt[1]); tt=tmp; return; } //cout<<tmp.size()<<'\n'; 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]); } } tt=convex; } ll f(int A,int B,int id) { if(id==-1)return 0; return A*tt[id].x+B*tt[id].y; } pi Find(int A,int B) { int lo=0; int hi=tt.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)tt.size()-1; i++) { ll cur=f(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}; } void Add_Pair(int X,int Y) { tt.push_back(point(X,Y)); } }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]); DP.Add_Pair(D[i],P[i]); } AP.build(); DP.build(); } ll BestSquad(int X, int Y) { pi CandAp=AP.Find(X,Y); pi CandDp=DP.Find(X,Y); //cout<<CandAp.fi<<' '<<CandDp.fi<<'\n'; ll ans=0; if(CandAp.fi!=CandDp.fi) { ans=AP.f(X,Y,CandAp.fi)+DP.f(X,Y,CandDp.fi); } else { ans=max(ans,AP.f(X,Y,CandAp.fi)+DP.f(X,Y,CandDp.se)); ans=max(ans,AP.f(X,Y,CandAp.se)+DP.f(X,Y,CandDp.fi)); } return ans; } /* int main() { Init({3, 2, 2, 4}, {1, 3, 1, 4}, {4, 3, 6, 1}); cout << BestSquad(1, 3) << '\n'; return 0; } */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...