#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#include<ext/rope>
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
template<class L, class R> istream &operator>>(istream &in, pair<L, R> &p){ return in >> p.first >> p.second; }
template<class Tuple, size_t ...Is> void read_tuple(istream &in, Tuple &t, index_sequence<Is...>){ ((in >> get<Is>(t)), ...); }
template<class ...Args> istream &operator>>(istream &in, tuple<Args...> &t){ read_tuple(in, t, index_sequence_for<Args...>{}); return in; }
template<class ...Args, template<class...> class T> istream &operator>>(enable_if_t<!is_same_v<T<Args...>, string>, istream> &in, T<Args...> &arr){ for(auto &x: arr) in >> x; return in; }
template<class L, class R> ostream &operator<<(ostream &out, const pair<L, R> &p){ return out << "(" << p.first << ", " << p.second << ")"; }
// template<class L, class R> ostream &operator<<(ostream &out, const pair<L, R> &p){ return out << p.first << " " << p.second << "\n"; }
template<class Tuple, size_t ...Is> void print_tuple(ostream &out, const Tuple &t, index_sequence<Is...>){ ((out << (Is ? " " : "") << get<Is>(t)), ...); }
template<class ...Args> ostream &operator<<(ostream &out, const tuple<Args...> &t){ print_tuple(out, t, index_sequence_for<Args...>{}); return out << "\n"; }
template<class ...Args, template<class...> class T> ostream &operator<<(enable_if_t<!is_same_v<T<Args...>, string>, ostream> &out, const T<Args...> &arr){ for(auto &x: arr) out << x << " "; return out << "\n"; }
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
mt19937_64 rngll(chrono::steady_clock::now().time_since_epoch().count());
#define all(a) a.begin(), a.end()
#define sz(a) (int)a.size()
typedef long long ll;
typedef vector<int> vi; typedef vector<ll> vl; typedef vector<double> vd; typedef vector<string> vs;
typedef pair<int, int> pii; typedef pair<ll, ll> pll; typedef pair<int, ll> pil; typedef pair<ll, int> pli;
typedef vector<pii> vpii; typedef vector<pil> vpil; typedef vector<pli> vpli; typedef vector<pll> vpll;
template<class T> T ctmax(T &x, const T &y){ return x = max(x, y); }
template<class T> T ctmin(T &x, const T &y){ return x = min(x, y); }
template<class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef tuple<int, int, int> tpl; typedef vector<tpl> vtpl;
template<class T = long long> struct point{
T x, y;
int ind;
template<class U> point(const point<U> &otr): x(otr.x), y(otr.y), ind(otr.ind){ }
template<class U = T, class V = T> point(U x = 0, V y = 0, int ind = -1): x(x), y(y), ind(ind){ }
template<class U> explicit operator point<U>() const{ return point<U>(static_cast<U>(x), static_cast<U>(y)); }
T operator*(const point &otr) const{ return x * otr.x + y * otr.y; }
T operator^(const point &otr) const{ return x * otr.y - y * otr.x; }
point operator+(const point &otr) const{ return {x + otr.x, y + otr.y}; }
point &operator+=(const point &otr){ return *this = *this + otr; }
point operator-(const point &otr) const{ return {x - otr.x, y - otr.y}; }
point &operator-=(const point &otr){ return *this = *this - otr; }
point operator-() const{ return {-x, -y}; }
#define scalarop_l(op) friend point operator op(const T &c, const point &p){ return {c op p.x, c op p.y}; }
scalarop_l(+) scalarop_l(-) scalarop_l(*) scalarop_l(/)
#define scalarop_r(op) point operator op(const T &c) const{ return {x op c, y op c}; }
scalarop_r(+) scalarop_r(-) scalarop_r(*) scalarop_r(/)
#define scalarapply(op) point &operator op(const T &c){ return *this = *this op c; }
scalarapply(+=) scalarapply(-=) scalarapply(*=) scalarapply(/=)
#define compareop(op) bool operator op(const point &otr) const{ return tie(x, y) op tie(otr.x, otr.y); }
compareop(>) compareop(<) compareop(>=) compareop(<=) compareop(==) compareop(!=)
#undef scalarop_l
#undef scalarop_r
#undef scalarapply
#undef compareop
double norm() const{ return sqrt(x * x + y * y); }
T squared_norm() const{ return x * x + y * y; }
double arg() const{ return atan2(y, x); } // [-pi, pi]
point<double> unit() const{ return point<double>(x, y) / norm(); }
point perp() const{ return {-y, x}; }
point<double> normal() const{ return perp().unit(); }
point<double> rotate(const double &theta) const{ return point<double>(x * cos(theta) - y * sin(theta), x * sin(theta) + y * cos(theta)); }
point reflect_x() const{ return {x, -y}; }
point reflect_y() const{ return {-x, y}; }
point reflect(const point &o) const{ return {2 * o.x - x, 2 * o.y - y}; }
bool operator||(const point &otr) const{ return !(*this ^ otr); }
};
template<class T> istream &operator>>(istream &in, point<T> &p){ return in >> p.x >> p.y; }
template<class T> ostream &operator<<(ostream &out, const point<T> &p){ return out << "(" << p.x << ", " << p.y << ")"; }
template<class T> double distance(const point<T> &p, const point<T> &q){ return (p - q).norm(); }
template<class T> T squared_distance(const point<T> &p, const point<T> &q){ return (p - q).squared_norm(); }
template<class T, class U, class V> T ori(const point<T> &p, const point<U> &q, const point<V> &r){ return (q - p) ^ (r - p); }
template<class IT> auto doubled_signed_area(IT begin, IT end){
class iterator_traits<IT>::value_type s = 0, init = *begin;
for(; begin != prev(end); ++ begin) s += *begin ^ *next(begin);
return s + (*begin ^ init);
}
template<class T> bool is_sorted(const point<T> &origin, point<T> p, point<T> q, point<T> r){
p -= origin, q -= origin, r -= origin;
T x = p ^ r, y = p ^ q, z = q ^ r;
return x >= 0 && y >= 0 && z >= 0 || x < 0 && (y >= 0 || z >= 0);
}
template<class T, class IT> bool is_sorted(const point<T> &origin, IT begin, IT end){
for(int i = 0; i < end - begin - 2; ++ i) if(!is_sorted(origin, begin + i, begin + i + 1, begin + i + 2)) return false;
return true;
}
template<class T = long long> struct line{
point<T> p, d; // p + d*t
template<class U = T, class V = T> line(point<U> p = {0, 0}, point<V> q = {0, 0}, bool Two_Points = true): p(p), d(Two_Points ? q - p : q){ }
template<class U> line(point<U> d): p(), d(static_cast<point<T>>(d)){ }
line(T a, T b, T c): p(a ? -c / a : 0, !a && b ? -c / b : 0), d(-b, a){ }
template<class U> explicit operator line<U>() const{ return line<U>(point<U>(p), point<U>(d), false); }
point<T> q() const{ return p + d; }
bool degen() const{ return d == point<T>(); }
tuple<T, T, T> coef() const{ return {d.y, -d.x, d.perp() * p}; } // d.y (X - p.x) - d.x (Y - p.y) = 0
bool operator||(const line<T> &L) const{ return d || L.d; }
};
template<class T> bool on_line(const point<T> &p, const line<T> &L){
if(L.degen()) return p == L.p;
return (p - L.p) || L.d;
}
template<class T> bool on_ray(const point<T> &p, const line<T> &L){
if(L.degen()) return p == L.p;
auto a = L.p - p, b = L.q() - p;
return (a || b) && a * L.d <= 0;
}
template<class T> bool on_segment(const point<T> &p, const line<T> &L){
if(L.degen()) return p == L.p;
auto a = L.p - p, b = L.q() - p;
return (a || b) && a * b <= 0;
}
template<class T> double distance_to_line(const point<T> &p, const line<T> &L){
if(L.degen()) return distance(p, L.p);
return abs((p - L.p) ^ L.d) / L.d.norm();
}
template<class T> double distance_to_ray(const point<T> &p, const line<T> &L){
if((p - L.p) * L.d <= 0) return distance(p, L.p);
return distance_to_line(p, L);
}
template<class T> double distance_to_segment(const point<T> &p, const line<T> &L){
if((p - L.p) * L.d <= 0) return distance(p, L.p);
if((p - L.q()) * L.d >= 0) return distance(p, L.q());
return distance_to_line(p, L);
}
template<class T> point<double> projection(const point<T> &p, const line<T> &L){ return static_cast<point<double>>(L.p) + (L.degen() ? point<double>() : (p - L.p) * L.d / L.d.norm() * static_cast<point<double>>(L.d)); }
template<class T> point<double> reflection(const point<T> &p, const line<T> &L){ return 2.0 * projection(p, L) - static_cast<point<double>>(p); }
template<class T> point<double> closest_point_on_segment(const point<T> &p, const line<T> &L){ return (p - L.p) * L.d <= 0 ? static_cast<point<double>>(L.p) : ((p - L.q()) * L.d >= 0 ? static_cast<point<double>>(L.q()) : projection(p, L)); }
template<int TYPE> struct EndpointChecker{ };
// For rays
template<> struct EndpointChecker<0>{ template<class T> bool operator()(const T& a, const T& b) const{ return true; } }; // For ray
// For closed end
template<> struct EndpointChecker<1>{ template<class T> bool operator()(const T& a, const T& b) const{ return a <= b; } }; // For closed end
// For open end
template<> struct EndpointChecker<2>{ template<class T> bool operator()(const T& a, const T& b) const{ return a < b; } }; // For open end
// Assumes parallel lines do not intersect
template<int LA, int LB, int RA, int RB, class T> pair<bool, point<double>> intersect_no_parallel_overlap(const line<T> &L, const line<T> &M){
auto s = L.d ^ M.d;
if(!s) return {false, point<double>()};
auto ls = (M.p - L.p) ^ M.d, rs = (M.p - L.p) ^ L.d;
if(s < 0) s = -s, ls = -ls, rs = -rs;
bool intersect = EndpointChecker<LA>()(decltype(ls)(0), ls) && EndpointChecker<LB>()(ls, s) && EndpointChecker<RA>()(decltype(rs)(0), rs) && EndpointChecker<RB>()(rs, s);
return {intersect, static_cast<point<double>>(L.p) + 1.0 * ls / s * static_cast<point<double>>(L.d)};
}
// Assumes parallel lines do not intersect
template<class T> pair<bool, point<double>> intersect_closed_segments_no_parallel_overlap(const line<T> &L, const line<T> &M){
return intersect_no_parallel_overlap<1, 1, 1, 1>(L, M);
}
// Assumes nothing
template<class T> pair<bool, line<double>> intersect_closed_segments(const line<T> &L, const line<T> &M){
auto s = L.d ^ M.d, ls = (M.p - L.p) ^ M.d;
if(!s){
if(ls) return {false, line<double>()};
auto Lp = L.p, Lq = L.q(), Mp = M.p, Mq = M.q();
if(Lp > Lq) swap(Lp, Lq);
if(Mp > Mq) swap(Mp, Mq);
line<double> res(max(Lp, Mp), min(Lq, Mq));
return {res.d >= point<double>(), res};
}
auto rs = (M.p - L.p) ^ L.d;
if(s < 0) s = -s, ls = -ls, rs = -rs;
bool intersect = 0 <= ls && ls <= s && 0 <= rs && rs <= s;
return {intersect, line<double>(static_cast<point<double>>(L.p) + 1.0 * ls / s * static_cast<point<double>>(L.d), point<double>())};
}
template<class T> double distance_between_rays(const line<T> &L, const line<T> &M){
if(L || M){
if(L.d * M.d >= 0 || (M.p - L.p) * M.d <= 0) return distance_to_line(L.p, M);
else return distance(L.p, M.p);
}
else{
if(intersect_no_parallel_overlap<1, 0, 1, 0, long long>(L, M).first) return 0;
else return min(distance_to_ray(L.p, M), distance_to_ray(M.p, L));
}
}
template<class T> double distance_between_segments(const line<T> &L, const line<T> &M){
if(intersect_closed_segments(L, M).first) return 0;
return min({distance_to_segment(L.p, M), distance_to_segment(L.q(), M), distance_to_segment(M.p, L), distance_to_segment(M.q(), L)});
}
template<class P> struct compare_by_angle{
const P origin;
compare_by_angle(const P &origin = P()): origin(origin){ }
bool operator()(const P &p, const P &q) const{ return ori(origin, p, q) > 0; }
};
template<class It, class P> void sort_by_angle(It begin, It end, const P &origin){
begin = partition(begin, end, [&origin](const decltype(*begin) &point){ return point == origin; });
auto pivot = partition(begin, end, [&origin](const decltype(*begin) &point) { return point > origin; });
compare_by_angle<P> cmp(origin);
sort(begin, pivot, cmp), sort(pivot, end, cmp);
}
/* Short Descriptions
struct point{
T x, y;
int ind;
double norm()
T squared_norm()
double arg()
point<double> unit()
point perp()
point<double> normal()
point<double> rotate(double theta)
point reflect_x()
point reflect_y()
point reflect(point o)
bool operator||(point otr)
};
double distance(point p, point q)
T squared_distance(point p, point q)
T ori(point p, point q, point r)
auto doubled_signed_area(IT begin, IT end)
bool is_sorted(point o, point p, point q, point r)
bool is_sorted(point o, IT begin, IT end)
struct line{
point p, d; // p + d*t
line(point p = {0, 0}, point<V> q = {0, 0}, bool Two_Points = true)
// two_points: pass through p and q
// else: pass through p, slope q
line(point<U> d) // pass through origin, slope d
line(T a, T b, T c) // declare with ax + by + c = 0
point<T> q()
bool degen()
tuple<T, T, T> coef()// d.y (X - p.x) - d.x (Y - p.y) = 0
};
bool on_line(point, line)
bool on_ray(point, line)
bool on_segment(point, line)
double distance_to_line(point, line)
double distance_to_ray(point, line)
double distance_to_segment(point, line)
point<double> projection(point, line)
point<double> reflection(point, line)
point<double> closest_point_on_segment(point, line)
// Endpoints: (0: rays), (1: closed), (2: open)
// Assumes parallel lines do not intersect
pair<bool, point<double>> intersect_no_parallel_overlap<EP1, EP2, EP3, EP4>(line, line)
// Assumes parallel lines do not intersect
pair<bool, point<double>> intersect_closed_segments_no_parallel_overlap(line, line)
// Assumes nothing
pair<bool, line<double>> intersect_closed_segments(line, line)
double distance_between_rays(line, line)
double distance_between_segments(line, line)
struct compare_by_angle
void sort_by_angle(It begin, It end, const P &origin) */
template<class T>
struct convex_hull: pair<vector<point<T>>, vector<point<T>>>{ // (Lower, Upper) type {0: both, 1: lower, 2: upper}
int type;
convex_hull(vector<point<T>> arr = vector<point<T>>(), int type = 0, bool is_sorted = false): type(type){
if(!is_sorted) sort(arr.begin(), arr.end()), arr.erase(unique(arr.begin(), arr.end()), arr.end());;
#define ADDP(C, cmp) while((int)C.size() > 1 && ori(C[(int)C.size() - 2], p, C.back()) cmp 0) C.pop_back(); C.push_back(p);
for(auto &p: arr){
if(type < 2){ ADDP(this->first, >=) }
if(!(type & 1)){ ADDP(this->second, <=) }
}
reverse(this->second.begin(), this->second.end());
}
vector<point<T>> get_hull() const{
if(type) return type == 1 ? this->first : this->second;
if(sz(this->first) <= 1) return this->first;
vector<point<T>> res(this->first);
res.insert(res.end(), ++ this->second.begin(), -- this->second.end());
return res;
}
int min_element(const point<T> &p) const{
assert(p.y >= 0 && !this->first.empty());
int low = 0, high = sz(this->first);
while(high - low > 2){
int mid1 = (2 * low + high) / 3, mid2 = (low + 2 * high) / 3;
p * this->first[mid1] >= p * this->first[mid2] ? low = mid1 : high = mid2;
}
int res = low;
for(int i = low + 1; i < high; i ++) if(p * this->first[res] > p * this->first[i]) res = i;
return res;
}
int max_element(const point<T> &p) const{
assert(p.y >= 0 && !this->second.empty());
int low = 0, high = sz(this->second);
while(high - low > 2){
int mid1 = (2 * low + high) / 3, mid2 = (low + 2 * high) / 3;
p * this->second[mid1] <= p * this->second[mid2] ? low = mid1 : high = mid2;
}
int res = low;
for(int i = low + 1; i < high; ++ i) if(p * this->second[res] < p * this->second[i]) res = i;
return res;
}
vector<point<T>> linearize() const{
if(type == 1) return this->first;
if(type == 2){ vector<point<T>> res(this->second); reverse(res.begin(), res.end()); return res; }
if(sz(this->first) <= 1) return this->first;
vector<point<T>> res;
res.reserve((int)this->first.size() + (int)this->second.size());
merge(all(this->first), ++ this->second.rbegin(), -- this->second.rend(), back_inserter(res));
return res;
}
convex_hull operator^(const convex_hull &otr) const{
vector<point<T>> temp, A = linearize(), B = otr.linearize();
temp.reserve((int)A.size() + (int)B.size());
merge(A.begin(), A.end(), B.begin(), B.end(), back_inserter(temp));
return {temp, type, true};
}
pair<vector<point<T>>, vector<point<T>>> get_boundary() const{
vector<point<T>> L(this->first), R(this->second);
for(int i = 1; i < (int)this->first.size(); ++ i) L[i] -= L[0];
for(int i = 1; i < (int)this->second.size(); ++ i) R[i] -= R[0];
return {L, R};
}
convex_hull operator+(const convex_hull &otr) const{
assert(type == otr.type);
compare_by_angle<class vector<point<T>>::value_type> cmp;
convex_hull res;
pair<vector<point<T>>, vector<point<T>>> A(this->get_boudnary()), B(otr.get_boudnary());
#define PROCESS(COND, X) \
if(COND && !A.X.empty() && !B.X.empty()){ \
res.X.reserve((int)A.X.size() + (int)B.X.size()); \
res.X.push_back(A.X.front() + B.X.front()); \
merge(A.X.begin() + 1, A.X.end(), B.X.begin() + 1, B.X.end(), back_inserter(res.X)); \
for(int i = 1; i < (int)res.X.size(); ++ i) res.X[i] += res.X[i - 1]; \
}
PROCESS(type < 2, first)
PROCESS(!(type & 1), second)
return res;
}
};
int n, na, nb;
vector<vector<convex_hull<long long>>> CH(2); // CH[i][j]: i=0(attack), i=1(defence), j=0(best), j=1(second best)
void Init(vi A, vi D, vi P){
n = sz(A);
vector<point<ll>> a(n), d(n);
for(int i = 0; i < n; ++ i){
a[i] = {A[i], P[i]};
d[i] = {D[i], P[i]};
a[i].ind = d[i].ind = i;
}
for(int k = 0; k < 2; ++ k){
CH[k].emplace_back(k ? d : a, 2);
vi used(n);
for(auto &p: CH[k][0].second){
used[p.ind] = true;
}
vector<point<ll>> temp;
for(int i = 0; i < n; ++ i){
if(!used[i]){
temp.push_back(k ? d[i] : a[i]);
}
}
CH[k].emplace_back(temp, 2);
}
na = sz(CH[0][0].second), nb = sz(CH[1][0].second);
}
ll BestSquad(int X, int Y){
int ia = CH[0][0].max_element({X, Y}), ib = CH[1][0].max_element({X, Y});
auto eval = [&](int i, int j, int k){
return CH[i][j].second[k] * point(X, Y);
};
if(CH[0][0].second[ia].ind == CH[1][0].second[ib].ind){
ll res = max(eval(0, 0, ia) + max(eval(1, 0, (ib - 1 + nb) % nb), eval(1, 0, (ib + 1) % nb)), max(eval(0, 0, (ia - 1 + na) % na), eval(0, 0, (ia + 1) % na)) + eval(1, 0, ib));
if(!CH[1][1].second.empty()){
ctmax(res, eval(0, 0, ia) + eval(1, 1, CH[1][1].max_element({X, Y})));
}
if(!CH[0][1].second.empty()){
ctmax(res, eval(0, 1, CH[0][1].max_element({X, Y})) + eval(1, 0, ib));
}
return res;
}
else{
return eval(0, 0, ia) + eval(1, 0, ib);
}
}
/*int main(){
cin.tie(0)->sync_with_stdio(0);
Init({3, 3, 5, 2, 1}, {2, 1, 1, 1, 4}, {5, 4, 3, 1, 2});
cout << BestSquad(2, 5) << "\n";
return 0;
}*/
/*
5
3 2 5
3 1 4
5 1 3
2 1 1
1 4 2
1
2 5
*/
////////////////////////////////////////////////////////////////////////////////////////
// //
// Coded by Aeren //
// //
////////////////////////////////////////////////////////////////////////////////////////
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
256 KB |
Output is correct |
| 2 |
Correct |
1 ms |
512 KB |
Output is correct |
| 3 |
Correct |
331 ms |
49896 KB |
Output is correct |
| 4 |
Correct |
330 ms |
50020 KB |
Output is correct |
| 5 |
Correct |
16 ms |
3880 KB |
Output is correct |
| 6 |
Correct |
258 ms |
55368 KB |
Output is correct |
| 7 |
Correct |
261 ms |
55308 KB |
Output is correct |
| 8 |
Correct |
260 ms |
55364 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
384 KB |
Output is correct |
| 2 |
Correct |
4 ms |
764 KB |
Output is correct |
| 3 |
Correct |
488 ms |
42856 KB |
Output is correct |
| 4 |
Correct |
491 ms |
49896 KB |
Output is correct |
| 5 |
Correct |
20 ms |
2268 KB |
Output is correct |
| 6 |
Correct |
644 ms |
49420 KB |
Output is correct |
| 7 |
Correct |
642 ms |
49480 KB |
Output is correct |
| 8 |
Correct |
628 ms |
49476 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
256 KB |
Output is correct |
| 2 |
Correct |
1 ms |
512 KB |
Output is correct |
| 3 |
Correct |
331 ms |
49896 KB |
Output is correct |
| 4 |
Correct |
330 ms |
50020 KB |
Output is correct |
| 5 |
Correct |
16 ms |
3880 KB |
Output is correct |
| 6 |
Correct |
258 ms |
55368 KB |
Output is correct |
| 7 |
Correct |
261 ms |
55308 KB |
Output is correct |
| 8 |
Correct |
260 ms |
55364 KB |
Output is correct |
| 9 |
Correct |
0 ms |
384 KB |
Output is correct |
| 10 |
Correct |
4 ms |
764 KB |
Output is correct |
| 11 |
Correct |
488 ms |
42856 KB |
Output is correct |
| 12 |
Correct |
491 ms |
49896 KB |
Output is correct |
| 13 |
Correct |
20 ms |
2268 KB |
Output is correct |
| 14 |
Correct |
644 ms |
49420 KB |
Output is correct |
| 15 |
Correct |
642 ms |
49480 KB |
Output is correct |
| 16 |
Correct |
628 ms |
49476 KB |
Output is correct |
| 17 |
Correct |
74 ms |
2808 KB |
Output is correct |
| 18 |
Correct |
7 ms |
820 KB |
Output is correct |
| 19 |
Correct |
514 ms |
49896 KB |
Output is correct |
| 20 |
Correct |
524 ms |
50036 KB |
Output is correct |
| 21 |
Correct |
30 ms |
2504 KB |
Output is correct |
| 22 |
Correct |
919 ms |
55368 KB |
Output is correct |
| 23 |
Correct |
949 ms |
55368 KB |
Output is correct |
| 24 |
Correct |
931 ms |
55368 KB |
Output is correct |
