Submission #154511

#	Time	Username	Problem	Language	Result	Execution time	Memory
154511		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;

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]));
	sort(all(t), [](const vec &a, const vec &b) {
		return cross(a, b) < 0;
	});
	int i, j;
	i = j = 0;
	while(i < t.size()) {
		vec c(0, 0);
		while(j < t.size() && cross(t[i], t[j]) == 0) {
			if(norm(c) < norm(t[j]))
				c = t[j];
			j++;
		}
		v.pb(c);
		i = j;
	}
	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, b) < 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);
	}
	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);
	}
	return ans;
}

Compilation message (stderr)

squad.cpp: In function 'void Init(std::vector<int>, std::vector<int>, std::vector<int>)':
squad.cpp:33:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while(i < t.size()) {
        ~~^~~~~~~~~~
squad.cpp:35:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(j < t.size() && cross(t[i], t[j]) == 0) {
         ~~^~~~~~~~~~

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