제출 #148533

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
148533		Ian and 2-bit memory (#200)	최적의 팀 구성 (FXCUP4_squad)	C++17	100 / 100	2021 ms	78908 KiB

squad

#include <bits/stdc++.h>

using namespace std;

#include "squad.h"

// [Convex Hull Trick (CHT)]
// https://github.com/kth-competitive-programming/kactl/blob/master/content/data-structures/LineContainer.h
// https://wcipeg.com/wiki/Convex_hull_trick
// Add lines of the form kx + m
// Query maximum values at points x

template<typename T>
struct CHTLine {
	T k, m;
	mutable T p;
	int id;
	CHTLine(T k_, T m_, T p_, int id_) : k(k_), m(m_), p(p_), id(id_) {}
	bool operator<(const CHTLine<T>& o) const {
		return k < o.k;
	}
	bool operator<(const T& x) const {
		return p < x;
	}
};

template<typename T>
constexpr T CHTINF;

template<>
constexpr int CHTINF<int> = INT_MAX;

template<>
constexpr long long CHTINF<long long> = LLONG_MAX;

template<>
constexpr float CHTINF<float> = HUGE_VALF;

template<>
constexpr double CHTINF<double> = HUGE_VAL;

template<>
constexpr long double CHTINF<long double> = HUGE_VALL;

template<typename T>
struct CHTMultiset : multiset<CHTLine<T>, less<>> {
	// reimplemented below for integral T
	T Divide(T a, T b) {
		return a / b;
	}
	using Iterator = typename multiset<CHTLine<T>, less<>>::iterator;
	bool Intersect(Iterator x, Iterator y) {
		if (y == this->end()) {
			x->p = CHTINF<T>;
			return false;
		}
		if (x->k == y->k)
			x->p = x->m > y->m ? CHTINF<T> : -CHTINF<T>;
		else
			x->p = Divide(y->m - x->m, x->k - y->k);
		return x->p >= y->p;
	}
	void Add(T k, T m, int id, CHTMultiset<T>* ptr) {
		Iterator z = this->emplace(k, m, 0, id);
		Iterator y = z++;
		Iterator x = y;
		while (Intersect(y, z)) {
			if (ptr) {
				ptr->Add(z->k, z->m, z->id, 0);
			}
			z = this->erase(z);
		}
		if (x != this->begin() && Intersect(--x, y)) {
			if (ptr) {
				ptr->Add(y->k, y->m, y->id, 0);
			}
			Intersect(x, y = this->erase(y));
			}
		while ((y = x) != this->begin() && (--x)->p >= y->p) {
			if (ptr) {
				ptr->Add(y->k, y->m, y->id, 0);
			}
			Intersect(x, this->erase(y));
			}
	}
	Iterator Query(T x) {
		// assert(!this->empty());
		return this->lower_bound(x);
		// return l.k * x + l.m;
	}
};

#define FLOOR_DIV(a, b) ((a) / (b) - (((a) ^ (b)) < 0 && (a) % (b)))

template<>
int CHTMultiset<int>::Divide(int a, int b) {
	return FLOOR_DIV(a, b);
}

template<>
long long CHTMultiset<long long>::Divide(long long a, long long b) {
	return FLOOR_DIV(a, b);
}

#undef FLOOR_DIV

CHTMultiset<long double> sa, sd, saa, sdd;
vector<int> aa, dd, pp;

// a * x + p * y
// (a + p * y / x) * x

void Init(std::vector<int> A, std::vector<int> D, std::vector<int> P){
	aa = A;
	dd = D;
	pp = P;
	int N = A.size();
	for (int i = 0; i < N; i++) {
		sa.Add(P[i], A[i], i, &saa);
		sd.Add(P[i], D[i], i, &sdd);
	}
	// for (auto it = sa.begin(); it != sa.end(); it++) printf("%d ", it->id);
	// puts("");
	// for (auto it = sd.begin(); it != sd.end(); it++) printf("%d ", it->id);
	// puts("");
}

long long ans;

void check(int i, int j, long long x, long long y) {
	// printf(" %d %d %lld\n", i, j, (aa[i] + dd[j]) * x + (pp[i] + pp[j]) * y);
	if (i != j) {
	ans = max(ans, (aa[i] + dd[j]) * x + (pp[i] + pp[j]) * y);
	}
	// i = 2, j = 3;
	// printf("  %d %d %lld\n", i, j, (aa[i] + dd[j]) * x + (pp[i] + pp[j]) * y);
}

long long BestSquad(int X, int Y){
	ans = LLONG_MIN;
	long double x = (long double) Y / X;
	auto ia = sa.Query(x);
	auto ib = sd.Query(x);
	vector<int> va = {ia->id};
	if (!saa.empty())
		va.push_back(saa.Query(x)->id);
	if (ia != sa.begin()) va.push_back(prev(ia)->id);
	if (next(ia) != sa.end()) va.push_back(next(ia)->id);
	vector<int> vb = {ib->id};
	if (!sdd.empty())
		vb.push_back(sdd.Query(x)->id);
	if (ib != sd.begin()) vb.push_back(prev(ib)->id);
	if (next(ib) != sd.end()) vb.push_back(next(ib)->id);
	for (int i : va)for (int j : vb) check(i, j ,X, Y);
	return ans;
}

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