#include <bits/stdc++.h>
#define int long long
using namespace std;
template <typename T> struct Point {
T x, y;
Point() : x(0), y(0) {}
Point(T _x, T _y) : x(_x), y(_y) {}
Point operator+(const Point other) const {
return Point(x + other.x, y + other.y);
}
Point operator-(const Point other) const {
return Point(x - other.x, y - other.y);
}
Point operator*(const T lambda) const {
return Point(x * lambda, y * lambda);
}
Point operator/(const T lambda) const {
return Point(x / lambda, y / lambda);
}
bool operator<(const Point &other) const {
return tie(x, y) < tie(other.x, other.y);
}
bool operator==(const Point &other) const {
return tie(x, y) == tie(other.x, other.y);
}
bool operator>(const Point &other) const { return other < *this; }
bool operator!=(const Point &other) const { return !(*this == other); }
bool operator<=(const Point &other) const { return !(other < *this); }
bool operator>=(const Point &other) const { return other <= *this; }
friend ostream &operator<<(ostream &out, const Point &a) {
return out << a.x << " " << a.y;
}
friend istream &operator>>(istream &in, Point &a) { return in >> a.x >> a.y; }
friend T dot(const Point a, const Point b) { return a.x * b.x + a.y * b.y; }
friend T cross(const Point a, const Point b) { return a.x * b.y - a.y * b.x; }
friend T dis2(const Point a, const Point b) { return dot(b - a, b - a); }
};
using P = Point<int>;
struct Angle {
int x, y;
Angle() : x(0), y(0) {}
Angle(int _x, int _y) : x(_x), y(_y) {}
int half() const {
assert(x or y);
return y < 0 or (!y and x < 0);
}
friend bool operator<(Angle a, Angle b) {
return make_pair(a.half(), a.y * b.x) < make_pair(b.half(), a.x * b.y);
}
friend bool operator==(Angle a, Angle b) { return !(a < b) and !(b < a); }
};
const int MAXN = 1e4;
int iDeb[MAXN], iFin[MAXN];
int prefMax[MAXN], suffMax[MAXN], rangeSum[MAXN], maxSum[MAXN];
void pull(int node) {
prefMax[node] =
max(prefMax[2 * node], rangeSum[2 * node] + prefMax[2 * node + 1]);
suffMax[node] =
max(suffMax[2 * node + 1], rangeSum[2 * node + 1] + suffMax[2 * node]);
maxSum[node] = max({maxSum[2 * node], maxSum[2 * node + 1],
suffMax[2 * node] + prefMax[2 * node + 1]});
rangeSum[node] = rangeSum[2 * node] + rangeSum[2 * node + 1];
}
void build(int node, int l, int r) {
iDeb[node] = l, iFin[node] = r;
if (l == r)
return;
int m = (l + r) / 2;
build(2 * node, l, m);
build(2 * node + 1, m + 1, r);
}
void upd(int node, int pos, int x) {
if (iDeb[node] > pos or iFin[node] < pos)
return;
if (iDeb[node] == iFin[node]) {
rangeSum[node] = x;
prefMax[node] = suffMax[node] = maxSum[node] = max(0LL, x);
return;
}
upd(2 * node, pos, x);
upd(2 * node + 1, pos, x);
pull(node);
}
signed main(void) {
ios_base::sync_with_stdio(false);
cin.tie(0);
int nbPoints;
cin >> nbPoints;
vector<P> points(nbPoints);
vector<int> poids(nbPoints);
for (int i = 0; i < nbPoints; ++i)
cin >> points[i] >> poids[i];
vector<Angle> angles;
for (int i = 0; i < nbPoints; ++i)
for (int j = i + 1; j < nbPoints; ++j) {
P diff = points[j] - points[i];
if (diff.y < 0 or (diff.y == 0 and diff.x < 0))
diff = diff * (-1);
angles.emplace_back(diff.x, diff.y);
}
for (int i = 0; i < nbPoints; ++i) {
Angle a(points[i].x, points[i].y);
if (a.y < 0 or (a.y == 0 and a.x < 0))
a.x *= -1, a.y *= -1;
if (points[i].x or points[i].y)
angles.push_back(a);
}
sort(angles.begin(), angles.end());
angles.resize(unique(angles.begin(), angles.end()) - angles.begin());
int nbAngles = angles.size();
vector<vector<int>> withAngles(nbAngles);
for (int i = 0; i < nbPoints; ++i) {
for (int j = i + 1; j < nbPoints; ++j) {
P diff = points[j] - points[i];
if (diff.y < 0 or (diff.y == 0 and diff.x < 0))
diff = diff * (-1);
Angle a(diff.x, diff.y);
int id = lower_bound(angles.begin(), angles.end(), a) - angles.begin();
withAngles[id].push_back(i);
withAngles[id].push_back(j);
}
}
vector<int> ordreInit(nbPoints);
iota(ordreInit.begin(), ordreInit.end(), 0LL);
build(1, 0, nbPoints - 1);
const double theta = 1e-9;
double costheta = cos(theta), sintheta = sin(theta);
auto getComparator = [&](P dir) {
using PP = Point<double>;
PP dir2 = PP(dir.x * costheta - dir.y * sintheta,
dir.x * sintheta + dir.y * costheta);
return [&points, dir, dir2](int i, int j) {
if (cross(dir, points[i]) != cross(dir, points[j]))
return cross(dir, points[i]) < cross(dir, points[j]);
return dir2.x * (points[i].y - points[j].y) -
dir2.y * (points[i].x - points[j].y) <
0;
PP A(points[i].x, points[i].y);
PP B(points[j].x, points[j].y);
return cross(dir2, A) < cross(dir2, B);
Angle a(points[i].x, points[i].y);
Angle b(points[j].x, points[j].y);
return a < b;
if (cross(dir, points[i]) >= 0)
return dot(dir, points[i]) > dot(dir, points[j]);
return dot(dir, points[i]) < dot(dir, points[j]);
};
};
for (int iAngle = 0; iAngle < nbAngles; ++iAngle) {
sort(withAngles[iAngle].begin(), withAngles[iAngle].end());
withAngles[iAngle].resize(
unique(withAngles[iAngle].begin(), withAngles[iAngle].end()) -
withAngles[iAngle].begin());
P dir(angles[iAngle].x, angles[iAngle].y);
sort(withAngles[iAngle].begin(), withAngles[iAngle].end(),
getComparator(dir));
}
sort(ordreInit.begin(), ordreInit.end(), getComparator({1, 0}));
for (int i = 0; i < nbPoints; ++i)
upd(1, i, poids[ordreInit[i]]);
vector<int> curPos(nbPoints);
for (int i = 0; i < nbPoints; ++i)
curPos[ordreInit[i]] = i;
int ret = maxSum[1];
/*for (int x : ordreInit)
cout << x << ' ';
cout << endl;*/
for (int iAngle = 0; iAngle < nbAngles; ++iAngle) {
vector<int> &toUpdate = withAngles[iAngle];
vector<int> positions;
for (int &x : toUpdate)
positions.push_back(curPos[x]);
sort(positions.begin(), positions.end());
int nbUpd = positions.size();
for (int i = 0; i < nbUpd; ++i) {
upd(1, positions[i], poids[toUpdate[i]]);
curPos[toUpdate[i]] = positions[i];
}
for (int i = 0; i < nbUpd; ++i)
ordreInit[positions[i]] = toUpdate[i];
/*cout << "-------------\n";
cout << angles[iAngle].x << ' ' << angles[iAngle].y << endl;
for (int x : toUpdate)
cout << x << ' ';
cout << endl;
for (int x : ordreInit)
cout << x << ' ';
cout << endl;*/
ret = max(ret, maxSum[1]);
}
cout << ret << endl;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
1108 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
712 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
712 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
712 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
1108 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
