Submission #154518

#	Time	Username	Problem	Language	Result	Execution time	Memory
154518		kostia244	Organizing the Best Squad (FXCUP4_squad)	C++17	0 / 100	2 ms	376 KiB

squad

#include "squad.h"
#include<bits/stdc++.h>
#define pb push_back
#define all(x) x.begin(), x.end()
using namespace std;
using ll = long long;
using vi = vector<ll>;
int n;
vi a, d, p;
using vec = complex<ll>;
ll dot(vec a, vec b) {
	return (conj(a) * b).real();
}
ll cross(vec a, vec b) {
	return (conj(a) * b).imag();
}
vector<vec> v;
	vec p0 = { 0, 0 };

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

void Init(std::vector<int> xA, std::vector<int> xD, std::vector<int> xP) {
	n = xA.size();
	for (auto i : xA)
		a.pb(i);
	for (auto i : xD)
		d.pb(i);
	for (auto i : xP)
		p.pb(i);

	vector<vec> t;
	for (int i = 0; i < n; i++)
		t.pb(vec(a[i], p[i]));
	for (auto i : t)
		if(p0.real() < i.real() || (p0.real() == i.real() && p0.imag() > i.imag()))
			p0 = i;
	sort(all(t), [&p0](const vec &a, const vec &b) {
		return cross(a-p0, b-p0) < 0;
	});
	v = {p0};
	for(auto i : t) {
		if(i == p0 || i == v.back()) continue;
		while(to_remove())
			swap(v.back(), v[v.size()-2]), v.pop_back();
		v.pb(i);
	}

	sort(all(p), greater<ll>());
}

long long BestSquad(int X, int Y) {
	ll ans = 0;
	auto it = upper_bound(all(v), vec(X, Y), [](const vec &a, const vec &b) {
		return cross(a-p0, b-p0) < 0;
	});
	if (it != v.end()) {
		ll t = X + dot(*it, vec(X, Y));
		if (it->imag() == p[0])
			t += Y * 1ll * p[1];
		else
			t += Y * 1ll * p[0];
		ans = max(ans, t);
	}
	auto itt = it;
	if (it != v.begin()) {
		--it;
		ll t = X + dot(*it, vec(X, Y));
		if (it->imag() == p[0])
			t += Y * 1ll * p[1];
		else
			t += Y * 1ll * p[0];
		ans = max(ans, t);
	}
	it = itt;
	if (it != v.end()) {
		++it;
		if (it != v.end()) {
			ll t = X + dot(*it, vec(X, Y));
			if (it->imag() == p[0])
				t += Y * 1ll * p[1];
			else
				t += Y * 1ll * p[0];
			ans = max(ans, t);
		}
	}
	// for(auto it : v) {
	// 		ll t = X+dot(it, vec(X, Y));
	// 		if(it.imag() == p[0])
	// 			t += Y*1ll*p[1];
	// 		else
	// 			t += Y*1ll*p[0];
	// 		ans = max(ans, t);
	// 		cout << it.real() << " " << it.imag() << " " << cross(vec(X, Y), it) << " " << t << "\n";
	// 	}
	return ans;
}

Compilation message (stderr)

squad.cpp: In function 'void Init(std::vector<int>, std::vector<int>, std::vector<int>)':
squad.cpp:41:17: warning: capture of variable 'p0' with non-automatic storage duration
  sort(all(t), [&p0](const vec &a, const vec &b) {
                 ^~
squad.cpp:18:6: note: 'vec p0' declared here
  vec p0 = { 0, 0 };
      ^~

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