제출 #154763

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
154763		kostia244	최적의 팀 구성 (FXCUP4_squad)	C++17	0 / 100	2 ms	256 KiB

squad

#include "squad.h"
//#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//#pragma GCC optimize ("trapv")
#include<bits/stdc++.h>
//#include<ext/pb_ds/tree_policy.hpp>
//#include<ext/pb_ds/assoc_container.hpp>
#define pb push_back
#define eb emplace_back
#define __V vector
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define oit ostream_iterator
#define mod 1000000007ll
#define print(x) for(auto i : (x)) cout << i << " ";cout << "\n";
#define printd(x) for(auto i : (x)) cout << i << " ";cout << #x << "\n";
using namespace std;
//using namespace __gnu_pbds;
void doin() {
	cin.tie();
	cout.tie();
	ios::sync_with_stdio(0);
#ifndef ONLINE_JUDGE
//	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
}
template<typename X, typename Y>
istream& operator>>(istream& in, pair<X, Y> &a) {
	in >> a.first >> a.second;
	return in;
}
template<typename T>
void getv(T& i) {
	cin >> i;
}
template<typename T, typename ... Ns>
void getv(vector<T>& v, int n, Ns ... ns) {
	v.resize(n);
	for (auto& i : v)
		getv(i, ns...);
}
template<typename T>
void getv1(T& i) {
	cin >> i;
}
template<typename T, typename ... Ns>
void getv1(vector<T>& v, int n, Ns ... ns) {
	v.resize(n + 1);
	for (int i = 1; i <= n; i++)
		getv1(v[i], ns...);
}
#ifdef _WIN32
#define getchar_unlocked() _getchar_nolock()
#define _CRT_DISABLE_PERFCRIT_LOCKS
#endif
inline void getch(char &X) {
	while (X = getchar_unlocked(), X < 33) {
		;
	}
}
inline void getstr(string &str) {
	str.clear();
	char cur;
	while (cur = getchar_unlocked(), cur < 33) {
		;
	}
	while (cur > 32) {
		str += cur;
		cur = getchar_unlocked();
	}
}
template<typename T> inline bool sc(T &num) {
	bool neg = 0;
	int c;
	num = 0;
	while (c = getchar_unlocked(), c < 33) {
		if (c == EOF)
			return false;
	}
	if (c == '-') {
		neg = 1;
		c = getchar_unlocked();
	}
	for (; c > 47; c = getchar_unlocked())
		num = num * 10 + c - 48;
	if (neg)
		num *= -1;
	return true;
}
template<typename a, typename b>
void minq(a& X, b Y) {
	if (X > Y)
		X = Y;
}
template<typename a, typename b>
void maxq(a& X, b Y) {
	if (X < Y)
		X = Y;
}
typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
typedef ll _I;
typedef pair<_I, _I> pi;
typedef pair<ld, ld> pd;
typedef map<_I, _I> mii;
typedef __V <_I> vi;
typedef __V <char> vc;
typedef __V <string> vs;
typedef __V <ld> vd;
typedef __V <vd> vvd;
typedef __V <pi> vpi;
typedef __V <__V<_I>> vvi;
typedef __V <__V<char>> vvc;
typedef __V <__V<pi>> vvpi;
using AntonTsypko = void;
using arsijo = AntonTsypko;
using god = arsijo;
//store differences, not the elements for rsq in fenwick or array(for write-only)
//Sum Over Subsets + inclusion-exclusion is a thing! (Solved div1E (383E) using it!)
//SQRT-heuristic divide items into groups: >sqrt and <=sqrt and do something according to group(eg. trie for one, z-func for other) - 1202E
//f-e+v=2
uniform_real_distribution<double> double_dist(0, 1);
uniform_int_distribution<int> dist(31, 55);
//WHEN DOING MODULAR SUBTRACTION ALWAYS **ALWAYS** ADD MOD
//don't use AVX at AtCoder(=RE)
//Trie: MAXDEPTH!=MAXSIZE
//suspiciously big numbers? use python, seriosly you don't wanna waste your time if it overflows
//MULTISET NOT SET
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//SQRT IS PROBABLY THE ANSWER
//SET TO ZERO
//typedef tree<int, null_type, greater<int>, rb_tree_tag,
//		tree_order_statistics_node_update> ordered_set; // order_of_key, find_by_order
using vec = complex<ll>;
#define x real()
#define y imag()
ll dot(vec a, vec b) {
	return (conj(a) * b).x;
}
ll cross(vec a, vec b) {
	return (conj(a) * b).y;
}
struct maxhull {
	vector<vec> hull, pts;

	bool to_remove() {
		int n = hull.size();
		if (n < 3)
			return false;
		return cross(hull[n - 2] - hull[n - 3], hull[n - 2] - hull[n - 1]) >= 0;
	}

	void buildUpperHull() {
		sort(all(pts), [](const vec& a, const vec& b) {
			return a.x < b.x || (a.x == b.x && a.y < b.y);
		});
		for (auto i : pts) {
			while (to_remove()) {
				swap(hull.back(), pts[hull.size() - 2]);
				hull.pop_back();
			}
			hull.pb(i);
		}
	}

	pair<vec, vec> query(vec v) {
		int lo = 0, hi = hull.size() - 1, a, b;
		while (hi - lo > 3) {
			a = lo + (hi - lo + 1) / 3;
			b = hi - (hi - lo + 1) / 3;
			if (dot(v, hull[a]) < dot(v, hull[b]))
				lo = a;
			else
				hi = b;
		}
		pair<vec, vec> ans(vec(0, 0), vec(0, 0));
		for (int i = max(0, lo-2); i <= min((int)hull.size()-1, hi+2); i++) {
			ll t = dot(v, hull[i]);
			if(t > dot(v, ans.first))
				ans.second = ans.first, ans.first = hull[i];
			else if(t > dot(v, ans.second))
				ans.second = hull[i];
		}
		return ans;
	}
};
int n;
vector<ll> p;
maxhull m;
void Init(std::vector<int> A, std::vector<int> D, std::vector<int> P){
	n = A.size();
	for(auto i : P) p.pb(i);
	for(int i = 0; i < n; i++)
		m.pts.pb(vec(A[i], P[i]));
	m.buildUpperHull();
	sort(all(p), greater<ll>());
}

long long BestSquad(int X, int Y){
	ll ans = 0;
	pair<vec, vec> a = m.query(vec(X, Y));
	if(a.first.y != p[0]) {
		ans = dot(a.first, vec(X, Y)) + Y*1ll*p[0] + X;
	} else {
		ans = dot(a.first, vec(X, Y)) + Y*1ll*p[1] + X;
		maxq(ans,dot(a.second, vec(X, Y)) + Y*1ll*p[0] + X);
	}
	return ans;
}

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