oj.uz

답안 #154809

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
154809 2019-09-24T18:46:35 Z kostia244 최적의 팀 구성 (FXCUP4_squad) C++17
100 / 100
 938 ms 49720 KB 
//#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;
}
 
using vvec = vector<vec>;
struct maxhull {
	bool better(const vec &v, const vec &a, const vec &b) const {
		return dot(v, a) > dot(v, b) || (dot(v, a) == dot(v, b) && a.y < b.y);
	}
 
	vvec pts, hulla, hullb;
	bool to_remove(vvec &hull) {
		int n = hull.size();
		if(n < 3) return false;
		return cross(hull[n-2]-hull[n-3], hull[n-1]-hull[n-2]) > 0;
	}
	void upperhull(vvec &pts, vvec& hull, vvec &dump) {
		sort(all(pts), [](const vec &a, const vec &b) {
			return pi(a.x, a.y) < pi(b.x, b.y);
		});
		for(auto i : pts) {
			while(to_remove(hull)) {
				swap(hull.back(), hull[hull.size()-2]);
				dump.pb(hull.back());
				hull.pop_back();
			}
			hull.pb(i);
		}
	}
	void init() {
		vvec dump, dumpb;
		upperhull(pts, hulla, dump);
		upperhull(dump, hullb, dumpb);
	}
	pair<vec, vec> query(vvec &hull, 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(better(v, hull[b], hull[a]))
				lo = a;
			else
				hi = b;
		}
		pair<vec, vec> ans = {vec(0, 0), vec(0, 0)};
		for(int i = max(0, lo-3); i <= min((int)hull.size()-1, hi+3); i++) {
			if(better(v, hull[i], ans.first)) {
				ans.second = ans.first;
				ans.first = hull[i];
			} else if(better(v, hull[i], ans.second))
				ans.second = hull[i];
		}
		return ans;
	}
	pair<vec, vec> query(vec v) {
		pair<vec, vec> a = query(hulla, v);
		pair<vec, vec> b = query(hullb, v);
		if(better(v, b.first, a.second))
			a.second = b.first;
		return a;
	}
};
int n;
vector<ll> p;
maxhull dmg, def;
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++)
		dmg.pts.pb(vec(A[i], P[i]));
	for(int i = 0; i < n; i++)
		def.pts.pb(vec(D[i], P[i]));
	dmg.init();
	def.init();
	sort(all(p), greater<ll>());
	// for(auto i : m.hull)
		// cout << i << "\n";
}
 
long long BestSquad(int X, int Y){
	ll ans = 0;
	pair<vec, vec> a = dmg.query(vec(X, Y));
	pair<vec, vec> b = def.query(vec(X, Y));
	if(a.first.y != b.first.y) {
		ans = dot(a.first+b.first, vec(X, Y));
	} else {
		ans = dot(a.first+b.second, vec(X, Y));
		maxq(ans, dot(a.second+b.first, vec(X, Y)));
	}
	return ans;
}

Subtask #1
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 3 ms 504 KB Output is correct
3 Correct 373 ms 49460 KB Output is correct
4 Correct 390 ms 49500 KB Output is correct
5 Correct 20 ms 3184 KB Output is correct
6 Correct 310 ms 44764 KB Output is correct
7 Correct 298 ms 44720 KB Output is correct
8 Correct 300 ms 44848 KB Output is correct

Subtask #2
28.0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 6 ms 760 KB Output is correct
3 Correct 601 ms 46640 KB Output is correct
4 Correct 614 ms 46620 KB Output is correct
5 Correct 24 ms 2420 KB Output is correct
6 Correct 670 ms 43340 KB Output is correct
7 Correct 659 ms 43228 KB Output is correct
8 Correct 660 ms 42972 KB Output is correct

Subtask #3
53.0 / 53.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 3 ms 504 KB Output is correct
3 Correct 373 ms 49460 KB Output is correct
4 Correct 390 ms 49500 KB Output is correct
5 Correct 20 ms 3184 KB Output is correct
6 Correct 310 ms 44764 KB Output is correct
7 Correct 298 ms 44720 KB Output is correct
8 Correct 300 ms 44848 KB Output is correct
9 Correct 3 ms 376 KB Output is correct
10 Correct 6 ms 760 KB Output is correct
11 Correct 601 ms 46640 KB Output is correct
12 Correct 614 ms 46620 KB Output is correct
13 Correct 24 ms 2420 KB Output is correct
14 Correct 670 ms 43340 KB Output is correct
15 Correct 659 ms 43228 KB Output is correct
16 Correct 660 ms 42972 KB Output is correct
17 Correct 82 ms 5368 KB Output is correct
18 Correct 9 ms 888 KB Output is correct
19 Correct 641 ms 49720 KB Output is correct
20 Correct 636 ms 49632 KB Output is correct
21 Correct 33 ms 2804 KB Output is correct
22 Correct 844 ms 45760 KB Output is correct
23 Correct 821 ms 45520 KB Output is correct
24 Correct 938 ms 45568 KB Output is correct