#include "squad.h"
#include <bits/stdc++.h>
using namespace std;
using lint = long long;
struct Data {
Data() {}
Data(lint x, lint y, lint i) : x(x), y(y), i(i) {}
lint x, y, i;
lint f(lint a, lint b) { return a*x + b*y; }
bool operator<(const Data b) const { return x < b.x or (x == b.x and y > b.y); }
};
int ccw(Data a, Data b, Data c) {
lint k = a.x*b.y + b.x*c.y + c.x*a.y - b.x*a.y - c.x*b.y - a.x*c.y;
if (k>0) return 1;
if (k<0) return -1;
return 0;
}
struct cht {
vector<Data> v;
void add(Data p) {
while (v.size() >= 2 and ccw(v[v.size()-2], v[v.size()-1], p) >= 0) v.pop_back();
v.push_back(p);
}
Data find(lint a, lint b) {
int l = -1, r = v.size()-1;
while (l+1<r) {
int m = (l+r) / 2;
if (b * (v[m+1].y - v[m].y) >= - a * (v[m+1].x - v[m].x)) l = m;
else r = m;
}
return v[r];
}
lint second(lint a, lint b) {
int l = -1, r = v.size()-1;
while (l+1<r) {
int m = (l+r) / 2;
if (b * (v[m+1].y - v[m].y) >= - a * (v[m+1].x - v[m].x)) l = m;
else r = m;
}
lint ans = 0;
if (r > 0) ans = max(ans, v[r-1].f(a, b));
if (r < v.size()-1) ans = max(ans, v[r+1].f(a, b));
return ans;
}
} a1, a2, d1, d2;
int n;
struct human {
int a, d, p;
} a[300004];
void Init(vector<int> A, vector<int> D, vector<int> P){
n = A.size();
for (int i=0; i<n; i++) a[i] = (human) { A[i], D[i], P[i] };
sort(a, a+n, [](human x, human y) { return x.a < y.a or (x.a == y.a and x.p > y.p); });
for (int i=0; i<n; i++) a1.add(Data(a[i].a, a[i].p, i));
for (int i=0; i<n; i++) if (!binary_search(a1.v.begin(), a1.v.end(), Data(a[i].a, a[i].p, i))) a2.add(Data(a[i].a, a[i].p, i));
sort(a, a+n, [](human x, human y) { return x.d < y.d or (x.d == y.d and x.p > y.p); });
for (int i=0; i<n; i++) d1.add(Data(a[i].d, a[i].p, i));
for (int i=0; i<n; i++) if (!binary_search(d1.v.begin(), d1.v.end(), Data(a[i].d, a[i].p, i))) d2.add(Data(a[i].d, a[i].p, i));
}
long long BestSquad(int X, int Y){
Data a = a1.find(X, Y), d = d1.find(X, Y);
if (a.i != d.i) return a.f(X, Y) + d.f(X, Y);
else {
lint aa = max(a1.second(X, Y), a2.find(X, Y).f(X, Y)), dd = max(d1.second(X, Y), d2.find(X, Y).f(X, Y));
return max(a.f(X, Y) + dd, d.f(X, Y) + aa);
}
}
Compilation message
squad.cpp: In member function 'lint cht::second(lint, lint)':
squad.cpp:49:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (r < v.size()-1) ans = max(ans, v[r+1].f(a, b));
~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
6 ms |
384 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
6 ms |
384 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
