#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <cstring>
#include <unordered_map>
#include <unordered_set>
using namespace std;
#define ll long long
#define all(aaa) aaa.begin(), aaa.end()
#pragma warning(disable : 4996)
ll gcd(ll a, ll b) {
return a ? gcd(b % a, a) : b;
}
struct P {
int x, y, w;
void normalize() {
int g = gcd(x, y);
x /= g;
y /= g;
if (y < 0 || y == 0 && x < 0) {
x = -x;
y = -y;
}
}
bool operator < (const P &oth) const {
int q1 = x <= 0,
q2 = oth.x <= 0;
return q1 == q2 ? (x * oth.y - y * oth.x > 0) : q1 < q2;
}
};
struct Line {
ll a, b, c;
P orth_vec;
Line(P &p, P &q) {
a = p.y - q.y;
b = q.x - p.x;
c = -p.y * (q.x - p.x) + (q.y - p.y) * p.x;
int g = gcd(gcd(a, b), c);
a /= g;
b /= g;
c /= g;
if (a < 0 || a == 0 && b < 0) {
a = -a;
b = -b;
c = -c;
}
orth_vec = { q.y - p.y, p.x - q.x };
orth_vec.normalize();
}
bool operator < (const Line &oth) const {
if (a == oth.a)
return b == oth.b ? c < oth.c : b < oth.b;
return a < oth.a;
}
};
const ll INF = 1e18;
const int N = 2005;
P a[N];
ll t[N * 4], mnp[N * 4], mxp[N * 4], pref[N], up[N * 4];
int pos[N];
int n;
map<P, map<Line, vector<int>>> mp;
void mrg(int v) {
t[v] = max(t[v * 2], t[v * 2 + 1]);
t[v] = max(t[v], mxp[v * 2 + 1] - mnp[v * 2]);
mxp[v] = max(mxp[v * 2], mxp[v * 2 + 1]);
mnp[v] = min(mnp[v * 2], mnp[v * 2 + 1]);
}
void build(int v = 1, int L = 0, int R = n) {
if (L == R) {
t[v] = 0;
mxp[v] = mnp[v] = pref[L];
}
else {
int m = (L + R) >> 1;
build(v * 2, L, m);
build(v * 2 + 1, m + 1, R);
mrg(v);
}
}
void push(int v, int L, int R) {
if (up[v]) {
if (L != R) {
up[v * 2] += up[v];
up[v * 2 + 1] += up[v];
}
mnp[v] += up[v];
mxp[v] += up[v];
up[v] = 0;
}
}
void upd(int l, int r, int x, int v = 1, int L = 0, int R = n) {
push(v, L, R);
if (l > r)
return;
if (l == L && r == R) {
up[v] += x;
push(v, L, R);
}
else {
int m = (L + R) >> 1;
upd(l, min(m, r), x, v * 2, L, m);
upd(max(m + 1, l), r, x, v * 2 + 1, m + 1, R);
mrg(v);
}
}
P tmp[N];
void print() {
for (int i = 1; i <= n; i++) {
tmp[pos[i]] = a[i];
}
for (int i = 1; i <= n; i++)
cout << tmp[i].w << " ";
cout << "\n";
for (int i = 1; i <= n; i++)
cout << tmp[i].x << " " << tmp[i].y << "\n";
cout << "\n";
}
signed main() {
#ifdef HOME
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n;
for (int i = 1; i <= n; i++) {
int x, y, w;
cin >> x >> y >> w;
a[i] = { x, y, w };
}
sort(a + 1, a + n + 1, [](P &a, P &b) {
return a.x == b.x ? a.y > b.y : a.x < b.x;
});
for (int i = 1; i <= n; i++) {
pos[i] = i;
pref[i] = pref[i - 1] + a[i].w;
for (int j = i + 1; j <= n; j++) {
Line l(a[i], a[j]);
mp[l.orth_vec][l].push_back(i);
mp[l.orth_vec][l].push_back(j);
}
}
build();
for (auto &i : mp) {
for (auto &j : i.second) {
sort(all(j.second));
j.second.erase(unique(all(j.second)), j.second.end());
}
}
ll ans = t[1];
print();
for (auto &ev : mp) {
for (auto &l : ev.second) {
int lb = N, rb = -1;
for (int x : l.second) {
lb = min(lb, pos[x]);
rb = max(rb, pos[x]);
upd(pos[x], n, -a[x].w);
}
for (int x : l.second) {
pos[x] = rb - pos[x] + lb;
upd(pos[x], n, a[x].w);
}
}
///*if (t[1] == 17) {
// cout << "-> " << ev.first.x << " " << ev.first.y << "\n";
// print();
//}*/
//cout << "-> " << ev.first.x << " " << ev.first.y << "\n";
//cout << "ans : " << t[1] << "\n";
//print();
ans = max(ans, t[1]);
}
cout << ans;
return 0;
}
Compilation message
bulldozer.cpp:41:0: warning: ignoring #pragma warning [-Wunknown-pragmas]
#pragma warning(disable : 4996)
bulldozer.cpp: In member function 'void P::normalize()':
bulldozer.cpp:53:23: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
if (y < 0 || y == 0 && x < 0) {
~~~~~~~^~~~~~~~
bulldozer.cpp: In constructor 'Line::Line(P&, P&)':
bulldozer.cpp:79:23: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
if (a < 0 || a == 0 && b < 0) {
~~~~~~~^~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
512 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
1664 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
1664 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
1664 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
512 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
