#include <bits/stdc++.h>
using namespace std;
using namespace std::placeholders;
#define debug 0
#define llong long long
#define xx first
#define yy second
#define len(x) ((int)x.size())
#define rep(i,n) for (int i = -1; ++ i < n; )
#define rep1(i,n) for (int i = 0; i ++ < n; )
#define all(x) x.begin(), x.end()
#define clog if (debug) cerr
// #define rand __rand
// mt19937 rng(chrono::system_clock::now().time_since_epoch().count()); // or mt19937_64
// template<class T = int> T rand(T range = numeric_limits<T>::max()) {
// return (T)(rng() % range);
// }
#define maxn 2020
template<class Num>
int sign(Num num) { return num < 0 ? -1 : num > 0; }
#define data data__
struct data {
llong max_sum_subarr, max_left_sum, max_right_sum, sum;
data() {}
data(llong elm): max_sum_subarr(elm), max_left_sum(elm), max_right_sum(elm), sum(elm) {}
data(llong mss, llong mls, llong mrs, llong s):
max_sum_subarr(mss), max_left_sum(mls), max_right_sum(mrs), sum(s) {}
void inc(llong val) {
sum += val;
max_sum_subarr = max_left_sum = max_right_sum = sum;
}
};
data operator + (data& u, data& v) {
return data(
max({u.max_sum_subarr, v.max_sum_subarr, u.max_right_sum + v.max_left_sum}),
max(u.max_left_sum, u.sum + v.max_left_sum),
max(v.max_right_sum, v.sum + u.max_right_sum),
u.sum + v.sum
);
}
data it[maxn * 4];
int state[maxn * 4] = {0};
bool is_leaf[maxn * 4] = {0};
int cur_state = 0;
queue<int> upd_queue;
void do_upd() {
++cur_state;
for (; len(upd_queue); upd_queue.pop()) {
int u = upd_queue.front();
if (!is_leaf[u]) it[u] = it[u << 1] + it[u << 1 | 1];
if (u != 1 and state[u >> 1] != cur_state) {
state[u >> 1] = cur_state;
upd_queue.push(u >> 1);
}
}
}
int leaf[maxn];
void build_it(int i, int l, int r, function<llong(int)> getitem) {
if (l + 1 == r) {
leaf[l] = i;
is_leaf[i] = 1;
it[i] = data(getitem(l));
upd_queue.push(i);
}
if (l + 1 >= r) return ;
int mid = (l + r) / 2;
build_it(i << 1, l, mid, getitem);
build_it(i << 1 | 1, mid, r, getitem);
if (i == 1) do_upd();
}
struct line {
llong a, b, c; // ax + by + c = 0
line(llong a_ = 0, llong b_ = 0, llong c_ = 0) : a(a_), b(b_), c(c_) {}
line& norm() {
llong g = __gcd(a, b);
g = __gcd(g, c);
a /= g;
b /= g;
c /= g;
// the normal will point almost the same way as Oy
// also the line a == b == 0 does not "really" exist, no need to handle it.
if (b < 0 || (b == 0 and a < 0)) {
a = -a; b = -b; c = -c;
}
return *this;
}
template<class Point>
static line through_points(Point const& u, Point const& v) {
return line(
u.y - v.y,
- u.x + v.x,
u.x * v.y - u.y * v.x
).norm();
}
};
bool operator == (const line& lhs, const line& rhs) {
return lhs.a == rhs.a and lhs.b == rhs.b and lhs.c == rhs.c;
}
struct spot {
llong x, y, cost;
int pos;
spot(llong x_ = 0, llong y_ = 0, llong v = 0) : x(x_), y(y_), cost(v), pos(0) {}
};
struct cmp_line {
bool operator()(const line& lhs, const line& rhs) const {
int cross = sign(lhs.a * rhs.b - lhs.b * rhs.a);
if (cross == 0) return lhs.c < rhs.c;
return cross > 0;
}
};
int n;
spot* a[maxn]; // for the sake of keeping things in places, I used pointer.
int main(void) {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n;
rep(i, n) {
a[i] = new spot();
cin >> a[i]->x >> a[i]->y >> a[i]->cost;
}
sort(a, a + n, [](const spot* u, const spot* v) {
return (u->x == v->x) ? u->y > v->y : u->x < v->x;
});
rep(i, n) a[i]->pos = i;
vector<tuple<line, spot*, spot*>> groups;
groups.reserve(n * n);
auto t1 = std::chrono::high_resolution_clock::now();
rep(i, n) {
for (int f = i + 1; f < n; ++f) {
line ln = line::through_points(*a[i], *a[f]);
groups.emplace_back(ln, a[i], a[f]);
}
}
sort(groups.begin(), groups.end(), [](auto const& u, auto const& v) {
return cmp_line()(get<0>(u), get<0>(v));
});
build_it(1, 0, n, [](int u) { return a[u]->cost; });
llong ans = 0;
auto upd_ans = [&]() {
// clog << setw(3) << ans << ' ' << setw(3) << tree.max_sum_subarr << ": ";
// tree.dolog(); clog << endl;
do_upd();
ans = max(ans, it[1].max_sum_subarr);
};
upd_ans();
vector<tuple<llong, int, int>> ranges;
auto process = [&]() {
for (auto [c, min_pos, max_pos]: ranges) {
for (int i = min_pos + 1; i <= max_pos; ++i) {
it[leaf[i]].inc(-a[i]->cost);
it[leaf[min_pos]].inc(a[i]->cost);
upd_queue.push(leaf[i]);
}
upd_queue.push(leaf[min_pos]);
}
upd_ans();
for (auto [c, min_pos, max_pos]: ranges) {
for (int l = min_pos, r = max_pos; l < r; ++l, --r) {
swap(a[l]->pos, a[r]->pos);
swap(a[l], a[r]);
}
for (int i = min_pos + 1; i <= max_pos; ++i) {
it[leaf[i]].inc(a[i]->cost);
it[leaf[min_pos]].inc(-a[i]->cost);
upd_queue.push(leaf[i]);
}
upd_queue.push(leaf[min_pos]);
}
upd_ans();
};
line cur_line(1, 0, 0);
for (auto& [ln, p1, p2]: groups) {
if (cur_line.a != ln.a or cur_line.b != ln.b) {
// clog << "=== process" << endl;
process();
ranges.clear();
}
if (ranges.empty() or cur_line.c != ln.c) {
ranges.emplace_back(ln.c, n, 0);
}
for (auto& i: {p1, p2}) {
get<1>(ranges.back()) = min(get<1>(ranges.back()), i->pos);
get<2>(ranges.back()) = max(get<2>(ranges.back()), i->pos);
}
cur_line = ln;
// clog << "line : " << -ln.b << ' ' << ln.a << endl;
}
auto t2 = std::chrono::high_resolution_clock::now();
auto duration = std::chrono::duration_cast<std::chrono::milliseconds>( t2 - t1 ).count();
clog << duration ;
process();
cout << ans;
return 0;
}
Compilation message
bulldozer.cpp: In lambda function:
bulldozer.cpp:169:19: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
for (auto [c, min_pos, max_pos]: ranges) {
^
bulldozer.cpp:169:39: warning: unused variable 'c' [-Wunused-variable]
for (auto [c, min_pos, max_pos]: ranges) {
^
bulldozer.cpp:178:19: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
for (auto [c, min_pos, max_pos]: ranges) {
^
bulldozer.cpp:178:39: warning: unused variable 'c' [-Wunused-variable]
for (auto [c, min_pos, max_pos]: ranges) {
^
bulldozer.cpp: In function 'int main()':
bulldozer.cpp:194:16: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
for (auto& [ln, p1, p2]: groups) {
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
632 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
504 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
504 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
504 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
632 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
