oj.uz

답안 #149368

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
149368 2019-09-01T06:20:31 Z 还没编好(#3801, cauchysheep, fjzzq2002, apiad) 최적의 팀 구성 (FXCUP4_squad) C++17
47 / 100
 2808 ms 416340 KB 
#pragma GCC optimize("-Ofast","-funroll-all-loops","-ffast-math")
#include "squad.h"
#include <iostream>
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <time.h>
#include <stdlib.h>
#include <string>
#include <bitset>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <algorithm>
#include <sstream>
#include <stack>
#include <iomanip>
#include <assert.h>
using namespace std;
#define pb push_back
#define mp make_pair
typedef pair<int,int> pii;
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
#define fi first
#define se second
#define fe first
#define FO(x) {freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);}
#define Edg int M=0,fst[SZ],vb[SZ],nxt[SZ];void ad_de(int a,int b){++M;nxt[M]=fst[a];fst[a]=M;vb[M]=b;}void adde(int a,int b){ad_de(a,b);ad_de(b,a);}
#define Edgc int M=0,fst[SZ],vb[SZ],nxt[SZ],vc[SZ];void ad_de(int a,int b,int c){++M;nxt[M]=fst[a];fst[a]=M;vb[M]=b;vc[M]=c;}void adde(int a,int b,int c){ad_de(a,b,c);ad_de(b,a,c);}
#define es(x,e) (int e=fst[x];e;e=nxt[e])
#define esb(x,e,b) (int e=fst[x],b=vb[e];e;e=nxt[e],b=vb[e])
#define SZ 1111111
typedef pair<int,int> pll;
ll operator * (pll a,pll b)
{
	return a.fi*(ll)b.se-(ll)a.se*b.fi;
}
pll operator - (pll a,pll b)
{
	return pll(a.fi-b.fi,a.se-b.se);
}
pll operator + (pll a,pll b)
{
	return pll(a.fi+b.fi,a.se+b.se);
}
vector<pll> convex_hull(vector<pll> p)
{
	stable_sort(p.begin(),p.end());
	if(p.size()<=2) return p;
	vector<pll> h;
	for(int r=0;r<2;++r)
	{
		int l=h.size();
		for(auto x:p)
		{
			while((int)h.size()>l+1&&
			(h[h.size()-1]-h[h.size()-2])
			*(x-h[h.size()-2])<=0) h.pop_back();
			h.pb(x);
		}
		h.pop_back();
		reverse(p.begin(),p.end());
	}
	return h;
}
vector<pll> su(const vector<pll>& aa,const vector<pll>& bb)
{
//	vector<pll> g;
//	for(auto x:aa)
//	for(auto y:bb) g.pb(y+x);
//	g=convex_hull(g);
//	return g;
	static pll ans[SZ],a[SZ],b[SZ];
	int top,top1=aa.size(),top2=bb.size();
	for(int i=1;i<top1;++i) a[i]=aa[i]-aa[i-1];
	for(int i=1;i<top2;++i) b[i]=bb[i]-bb[i-1];
	a[top1]=aa[0]-aa[top1-1];
	b[top2]=bb[0]-bb[top2-1];
    //for(int i=1;i<=top1;i++)a[i]=stack1[i+1]-stack1[i];
    //for(int i=1;i<=top2;i++)b[i]=stack2[i+1]-stack2[i];
    ans[top=1]=aa[0]+bb[0];
    int now1=1,now2=1;
    while(now1<=top1&&now2<=top2)
		top++,ans[top]=ans[top-1]+
		((a[now1]*b[now2])>=0?a[now1++]:b[now2++]);
    while(now1<=top1)top++,ans[top]=ans[top-1]+a[now1++];
    while(now2<=top2)top++,ans[top]=ans[top-1]+b[now2++];
    top--;
	vector<pll> oo;
	for(int i=1;i<=top;++i) oo.pb(ans[i]);
	return oo;
}
int n,a[SZ],d[SZ],p[SZ];
vector<pll> op;
vector<pll> oa[SZ],ob[SZ];
void go(int l,int r,int i=1)
{
	if(l>=r)
	{
		for(int t=l;t<=r;++t)
			oa[i].pb(pll(a[t],p[t])),
			ob[i].pb(pll(d[t],p[t]));
		return;
	}
	int m=(l+r)>>1;
	go(l,m,i*2); go(m+1,r,i*2+1);
	vector<pll> &A=oa[i*2],&B=ob[i*2],&C=oa[i*2+1],&D=ob[i*2+1];
//	vector<pll> A(m-l+1),B(m-l+1),C(r-m),D(r-m);
//	for(int i=l;i<=m;++i)
//		A[i-l]=(pll(a[i],p[i])),
//		B[i-l]=(pll(d[i],p[i]));
//	for(int i=m+1;i<=r;++i)
//		C[i-m-1]=(pll(a[i],p[i])),
//		D[i-m-1]=(pll(d[i],p[i]));
	#define CH(w) w=convex_hull(w)
	CH(A);CH(B);CH(C);CH(D);
//	cout<<A.size()<<"w"<<B.size()<<"w"<<C.size()<<"w"<<D.size()<<"\n";
	for(auto t:su(A,D)) op.pb(t);
	for(auto t:su(B,C)) op.pb(t);
	for(auto t:C) A.pb(t);
	for(auto t:D) B.pb(t);
	swap(A,oa[i]);
	swap(B,ob[i]);
}
vector<pair<ld,pll>> sb;
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];
	go(0,n-1);
//	for(auto u:op) cout<<u.fi<<","<<u.se<<"!";
//	cout<<"\n";
	op=convex_hull(op);
	for(int j=0;j<op.size();++j)
	{
		pll P=op[j],Q=op[(j+1)%op.size()];
		sb.pb(mp((Q.se-P.se)/ld(Q.fi-P.fi),P));
	}
	sort(sb.begin(),sb.end());
}

long long BestSquad(int X, int Y){
	auto w=lower_bound(sb.begin(),sb.end(),mp(-X/ld(Y),pll(0,0)));
	for(int j=1;j<=8&&w!=sb.begin();++j)
		--w;
	ll mx=0;
	for(int j=1;j<=16&&w!=sb.end();++j)
	{
		mx=max(mx,X*(ll)w->se.fi+Y*(ll)w->se.se);
		++w;
	}
	return mx;
}
#ifdef LOCAL
#include "grader.cpp"
#endif

Compilation message

squad.cpp: In function 'void Init(std::vector<int>, std::vector<int>, std::vector<int>)':
squad.cpp:136:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int j=0;j<op.size();++j)
              ~^~~~~~~~~~

Subtask #1
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 39 ms 52608 KB Output is correct
2 Correct 43 ms 52992 KB Output is correct
3 Correct 1379 ms 157344 KB Output is correct
4 Correct 1349 ms 157468 KB Output is correct
5 Correct 177 ms 71896 KB Output is correct
6 Correct 2804 ms 416340 KB Output is correct
7 Correct 2808 ms 416340 KB Output is correct
8 Correct 2708 ms 416276 KB Output is correct

Subtask #2
28.0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Correct 40 ms 52608 KB Output is correct
2 Correct 50 ms 53236 KB Output is correct
3 Correct 1246 ms 141852 KB Output is correct
4 Correct 1218 ms 141852 KB Output is correct
5 Correct 110 ms 59884 KB Output is correct
6 Correct 2135 ms 276824 KB Output is correct
7 Correct 2138 ms 276824 KB Output is correct
8 Correct 2163 ms 276824 KB Output is correct

Subtask #3
0 / 53.0

# 결과 실행 시간 메모리 Grader output
1 Correct 39 ms 52608 KB Output is correct
2 Correct 43 ms 52992 KB Output is correct
3 Correct 1379 ms 157344 KB Output is correct
4 Correct 1349 ms 157468 KB Output is correct
5 Correct 177 ms 71896 KB Output is correct
6 Correct 2804 ms 416340 KB Output is correct
7 Correct 2808 ms 416340 KB Output is correct
8 Correct 2708 ms 416276 KB Output is correct
9 Correct 40 ms 52608 KB Output is correct
10 Correct 50 ms 53236 KB Output is correct
11 Correct 1246 ms 141852 KB Output is correct
12 Correct 1218 ms 141852 KB Output is correct
13 Correct 110 ms 59884 KB Output is correct
14 Correct 2135 ms 276824 KB Output is correct
15 Correct 2138 ms 276824 KB Output is correct
16 Correct 2163 ms 276824 KB Output is correct
17 Correct 116 ms 55160 KB Output is correct
18 Correct 53 ms 53656 KB Output is correct
19 Correct 1607 ms 157468 KB Output is correct
20 Correct 1668 ms 157468 KB Output is correct
21 Incorrect 147 ms 64484 KB Output isn't correct
22 Halted 0 ms 0 KB -