#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;
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]));
vec p0 = { 0, 0 };
for (auto i : t)
if(p0.imag() > i.imag() || (p0.imag() == i.imag() && p0.real() > i.real()))
p0 = i;
sort(all(t), [&p0](const vec &a, const vec &b) {
return a.real() < b.real();
});
p0 = t[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, 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);
}
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;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
256 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
256 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
