Submission #150841

#	Time	Username	Problem	Language	Result	Execution time	Memory
150841		还没编好 (#200)	Organizing the Best Squad (FXCUP4_squad)	C++17	0 / 100	3104 ms	300092 KiB

squad

#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;
}

• Subtask 1: 0 / 19
• Subtask 2: 0 / 28
• Subtask 3: 0 / 53