Submission #150841

#TimeUsernameProblemLanguageResultExecution timeMemory
150841还没编好 (#200)Organizing the Best Squad (FXCUP4_squad)C++17
0 / 100
3104 ms300092 KiB
#include "squad.h" #include <bits/stdc++.h> using namespace std; #define rep(i,a,n) for (int i=a;i<n;i++) #define per(i,a,n) for (int i=n-1;i>=a;i--) #define pb push_back #define mp make_pair #define all(x) (x).begin(),(x).end() #define fi first #define se second #define SZ(x) ((int)(x).size()) typedef vector<int> VI; typedef long long ll; typedef pair<int,int> PII; const ll mod=1000000007; ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;} ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;} // head const int N=301000; struct point { ll x,y; point() {} point(ll x,ll y):x(x),y(y) {} }; point operator + (const point &a, const point &b) { return point(a.x+b.x,a.y+b.y); } point operator - (const point &a, const point &b) { return point(a.x-b.x,a.y-b.y); } bool operator < (const point &a, const point &b) { return a.x<b.x||(a.x==b.x&&a.y<b.y); } vector<point> pt; bool cmp(point a,point b,point c) { // b在c上面 b=b-a; c=c-a; if (b.x==c.x) return 1; return b.y*c.x<=b.x*c.y; } vector<point> build(vector<point> &pt) { int t=-1; VI q(SZ(pt)+1,0); rep(i,0,SZ(pt)) { while (t>=1&&cmp(pt[q[t-1]],pt[q[t]],pt[i])) --t; q[++t]=i; } vector<point> qt(t+1); rep(i,0,t+1) qt[i]=pt[q[i]]; /* rep(i,0,SZ(pt)) printf("%lld,%lld\n",pt[i].x,pt[i].y); puts("---"); rep(i,0,SZ(qt)) printf("%lld,%lld\n",qt[i].x,qt[i].y); puts("---"); */ return qt; } vector<point> merge(vector<point> &pt,vector<point> &qt) { if (pt.empty()||qt.empty()) return vector<point>(0); vector<point> rt; /* rep(i,0,SZ(pt)) printf("%lld,%lld\n",pt[i].x,pt[i].y); puts("---"); rep(i,0,SZ(qt)) printf("%lld,%lld\n",qt[i].x,qt[i].y); puts("---");*/ rep(i,1,SZ(pt)) rt.pb(pt[i]-pt[i-1]); rep(i,1,SZ(qt)) rt.pb(qt[i]-qt[i-1]); sort(all(rt),[&](point &a,point &b) { return a.x*b.y<a.y*b.x; }); point p=pt[0]+qt[0]; // printf("faq %lld,%lld\n",p.x,p.y); rt.insert(rt.begin(),p); rep(i,1,SZ(rt)) rt[i]=rt[i-1]+rt[i]; // rep(i,0,SZ(rt)) printf("%lld,%lld\n",rt[i].x,rt[i].y); // puts("----"); return rt; } int a[N],d[N],p[N],n; PII pa[N],pd[N]; vector<point> ap; void Init(std::vector<int> A, std::vector<int> D, std::vector<int> P){ n=A.size(); for(int i=0;i<n;++i) { a[i]=A[i],d[i]=D[i],p[i]=P[i]; pa[i]=mp(a[i],i); pd[i]=mp(d[i],i); } sort(pa,pa+n); sort(pd,pd+n); rep(j,0,19) { vector<point> pt1,pt2; rep(i,0,n) { int id=pa[i].se; if (((id>>j)&1)==0) pt1.pb(point(a[id],p[id])); } rep(i,0,n) { int id=pd[i].se; if (((id>>j)&1)==1) pt2.pb(point(d[id],p[id])); } pt1=build(pt1); pt2=build(pt2); pt1=merge(pt1,pt2); for (auto p:pt1) ap.pb(p); pt1.clear(); pt2.clear(); rep(i,0,n) { int id=pa[i].se; if (((id>>j)&1)==1) pt1.pb(point(a[id],p[id])); } rep(i,0,n) { int id=pd[i].se; if (((id>>j)&1)==0) pt2.pb(point(d[id],p[id])); } pt1=build(pt1); pt2=build(pt2); pt1=merge(pt1,pt2); for (auto p:pt1) ap.pb(p); } sort(all(ap)); ap=build(ap); } long long BestSquad(int X, int Y){ ll ans=0; rep(i,0,SZ(ap)) ans=max(ans,X*ap[i].x+Y*ap[i].y); return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...