#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct Point {
ll x;
ll y;
ll value;
};
struct R {
int sgn;
ll up;
ll down;
int i;
int j;
};
R get(ll x, ll y) {
R sol;
sol.sgn = +1;
if (x < 0 && y < 0) {
x *= -1;
y *= -1;
}
if (x < 0 || y < 0) {
sol.sgn = -1;
}
sol.up = abs(x);
sol.down = abs(y);
return sol;
}
bool operator < (R a, R b) {
if (a.sgn != b.sgn) {
return a.sgn < b.sgn;
}
if (a.sgn == -1) {
swap(a, b);
}
return a.up * b.down < b.up * a.down;
}
bool initialCmp(Point a, Point b) {
if (a.y == b.y) {
return a.x < b.x;
}
return a.y < b.y;
}
const int N = 2000 + 7;
int n;
R panta[N][N];
Point points[N];
ll value[N];
void sneakyHack() {
for (int i = 1; i <= n; i++) {
swap(points[i].x, points[i].y);
}
}
int ord[N];
int inv[N];
struct Node {
ll sol;
ll sum;
ll pref;
ll suf;
};
Node operator + (Node a, Node b) {
ll sol = max(max(a.sol, b.sol), a.suf + b.pref);
ll sum = a.sum + b.sum;
ll pref = max(a.pref, a.sum + b.pref);
ll suf = max(b.suf, b.sum + a.suf);
return {sol, sum, pref, suf};
}
Node tree[4 * N];
void build(int v, int tl, int tr) {
if (tl == tr) {
tree[v] = {max(value[tl], 0LL), value[tl], max(value[tl], 0LL), max(value[tl], 0LL)};
} else {
int tm = (tl + tr) / 2;
build(2 * v, tl, tm);
build(2 * v + 1, tm + 1, tr);
tree[v] = tree[2 * v] + tree[2 * v + 1];
}
}
void upd(int v, int tl, int tr, int i) {
if (tr < i || i < tl) {
return;
}
if (tl == tr) {
tree[v] = {max(value[tl], 0LL), value[tl], max(value[tl], 0LL), max(value[tl], 0LL)};
} else {
int tm = (tl + tr) / 2;
upd(2 * v, tl, tm, i);
upd(2 * v + 1, tm + 1, tr, i);
tree[v] = tree[2 * v] + tree[2 * v + 1];
}
}
int main() {
bool isHome;
isHome = true;
isHome = false;
if (isHome) {
freopen ("input", "r", stdin);
} else {
ios::sync_with_stdio(0); cin.tie(0);
}
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> points[i].x >> points[i].y >> points[i].value;
}
ll best = 0;
for (int iteration = 1; iteration <= 2; iteration++) {
sneakyHack();
sort(points + 1, points + n + 1, initialCmp);
for (int i = 1; i <= n; i++) {
ord[i] = i;
inv[i] = i;
for (int j = i + 1; j <= n; j++) {
panta[i][j] = get(points[i].x - points[j].x, points[i].y - points[j].y);
panta[i][j].i = i;
panta[i][j].j = j;
}
value[i] = points[i].value;
}
vector<R> all;
for (int i = 1; i <= n; i++) {
for (int j = i + 1; j <= n; j++) {
all.push_back(panta[i][j]);
}
}
build(1, 1, n);
stable_sort(all.begin(), all.end());
best = max(best, tree[1].sol);
/// all[it] < all[it + 1]
int l = 0;
while (l < (int) all.size()) {
int r = l;
while (r + 1 < (int) all.size() && !(all[r] < all[r + 1])) {
r++;
}
for (int it = l; it <= r; it++) {
int i = all[it].i;
int j = all[it].j;
int pos_i = inv[i];
int pos_j = inv[j];
swap(ord[pos_i], ord[pos_j]);
inv[ord[pos_i]] = pos_i;
inv[ord[pos_j]] = pos_j;
swap(value[pos_i], value[pos_j]);
upd(1, 1, n, pos_i);
upd(1, 1, n, pos_j);
}
best = max(best, tree[1].sol);
l = r + 1;
}
}
cout << best << "\n";
return 0;
}
Compilation message
bulldozer.cpp: In function 'int main()':
bulldozer.cpp:117:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
117 | freopen ("input", "r", stdin);
| ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
1252 KB |
Output is correct |
2 |
Correct |
2 ms |
1252 KB |
Output is correct |
3 |
Correct |
3 ms |
1252 KB |
Output is correct |
4 |
Correct |
2 ms |
1252 KB |
Output is correct |
5 |
Correct |
2 ms |
1252 KB |
Output is correct |
6 |
Correct |
2 ms |
1252 KB |
Output is correct |
7 |
Correct |
2 ms |
1252 KB |
Output is correct |
8 |
Correct |
2 ms |
1252 KB |
Output is correct |
9 |
Correct |
4 ms |
1252 KB |
Output is correct |
10 |
Correct |
2 ms |
1252 KB |
Output is correct |
11 |
Correct |
0 ms |
332 KB |
Output is correct |
12 |
Correct |
0 ms |
332 KB |
Output is correct |
13 |
Correct |
0 ms |
332 KB |
Output is correct |
14 |
Correct |
0 ms |
332 KB |
Output is correct |
15 |
Correct |
0 ms |
332 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
1252 KB |
Output is correct |
2 |
Correct |
3 ms |
1252 KB |
Output is correct |
3 |
Correct |
3 ms |
1252 KB |
Output is correct |
4 |
Correct |
3 ms |
1252 KB |
Output is correct |
5 |
Correct |
3 ms |
1312 KB |
Output is correct |
6 |
Correct |
3 ms |
1252 KB |
Output is correct |
7 |
Correct |
3 ms |
1252 KB |
Output is correct |
8 |
Correct |
3 ms |
1252 KB |
Output is correct |
9 |
Correct |
5 ms |
1252 KB |
Output is correct |
10 |
Correct |
3 ms |
1252 KB |
Output is correct |
11 |
Correct |
0 ms |
332 KB |
Output is correct |
12 |
Correct |
1 ms |
332 KB |
Output is correct |
13 |
Correct |
0 ms |
332 KB |
Output is correct |
14 |
Correct |
0 ms |
332 KB |
Output is correct |
15 |
Correct |
0 ms |
332 KB |
Output is correct |
16 |
Correct |
1 ms |
332 KB |
Output is correct |
17 |
Correct |
0 ms |
332 KB |
Output is correct |
18 |
Correct |
1 ms |
332 KB |
Output is correct |
19 |
Correct |
1 ms |
332 KB |
Output is correct |
20 |
Correct |
0 ms |
332 KB |
Output is correct |
21 |
Correct |
5 ms |
1252 KB |
Output is correct |
22 |
Correct |
3 ms |
1252 KB |
Output is correct |
23 |
Correct |
3 ms |
1252 KB |
Output is correct |
24 |
Correct |
3 ms |
1252 KB |
Output is correct |
25 |
Correct |
3 ms |
1252 KB |
Output is correct |
26 |
Correct |
3 ms |
1252 KB |
Output is correct |
27 |
Correct |
4 ms |
1252 KB |
Output is correct |
28 |
Correct |
3 ms |
1252 KB |
Output is correct |
29 |
Correct |
3 ms |
1252 KB |
Output is correct |
30 |
Correct |
3 ms |
1252 KB |
Output is correct |
31 |
Correct |
3 ms |
1252 KB |
Output is correct |
32 |
Correct |
3 ms |
1252 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
1252 KB |
Output is correct |
2 |
Correct |
3 ms |
1252 KB |
Output is correct |
3 |
Correct |
3 ms |
1252 KB |
Output is correct |
4 |
Correct |
3 ms |
1252 KB |
Output is correct |
5 |
Correct |
3 ms |
1312 KB |
Output is correct |
6 |
Correct |
3 ms |
1252 KB |
Output is correct |
7 |
Correct |
3 ms |
1252 KB |
Output is correct |
8 |
Correct |
3 ms |
1252 KB |
Output is correct |
9 |
Correct |
5 ms |
1252 KB |
Output is correct |
10 |
Correct |
3 ms |
1252 KB |
Output is correct |
11 |
Correct |
0 ms |
332 KB |
Output is correct |
12 |
Correct |
1 ms |
332 KB |
Output is correct |
13 |
Correct |
0 ms |
332 KB |
Output is correct |
14 |
Correct |
0 ms |
332 KB |
Output is correct |
15 |
Correct |
0 ms |
332 KB |
Output is correct |
16 |
Correct |
1 ms |
332 KB |
Output is correct |
17 |
Correct |
0 ms |
332 KB |
Output is correct |
18 |
Correct |
1 ms |
332 KB |
Output is correct |
19 |
Correct |
1 ms |
332 KB |
Output is correct |
20 |
Correct |
0 ms |
332 KB |
Output is correct |
21 |
Correct |
5 ms |
1252 KB |
Output is correct |
22 |
Correct |
3 ms |
1252 KB |
Output is correct |
23 |
Correct |
3 ms |
1252 KB |
Output is correct |
24 |
Correct |
3 ms |
1252 KB |
Output is correct |
25 |
Correct |
3 ms |
1252 KB |
Output is correct |
26 |
Correct |
3 ms |
1252 KB |
Output is correct |
27 |
Correct |
4 ms |
1252 KB |
Output is correct |
28 |
Correct |
3 ms |
1252 KB |
Output is correct |
29 |
Correct |
3 ms |
1252 KB |
Output is correct |
30 |
Correct |
3 ms |
1252 KB |
Output is correct |
31 |
Correct |
3 ms |
1252 KB |
Output is correct |
32 |
Correct |
3 ms |
1252 KB |
Output is correct |
33 |
Correct |
1788 ms |
164832 KB |
Output is correct |
34 |
Correct |
1783 ms |
164936 KB |
Output is correct |
35 |
Correct |
1791 ms |
164892 KB |
Output is correct |
36 |
Correct |
1773 ms |
164832 KB |
Output is correct |
37 |
Correct |
1784 ms |
164900 KB |
Output is correct |
38 |
Correct |
1807 ms |
164812 KB |
Output is correct |
39 |
Correct |
1836 ms |
164856 KB |
Output is correct |
40 |
Correct |
1834 ms |
164900 KB |
Output is correct |
41 |
Correct |
1777 ms |
164892 KB |
Output is correct |
42 |
Correct |
1773 ms |
164824 KB |
Output is correct |
43 |
Correct |
1746 ms |
164844 KB |
Output is correct |
44 |
Correct |
1730 ms |
164888 KB |
Output is correct |
45 |
Correct |
1734 ms |
165012 KB |
Output is correct |
46 |
Correct |
1745 ms |
164864 KB |
Output is correct |
47 |
Correct |
1735 ms |
164816 KB |
Output is correct |
48 |
Correct |
1745 ms |
164808 KB |
Output is correct |
49 |
Correct |
1741 ms |
164808 KB |
Output is correct |
50 |
Correct |
1770 ms |
164944 KB |
Output is correct |
51 |
Correct |
1743 ms |
164808 KB |
Output is correct |
52 |
Correct |
1742 ms |
164980 KB |
Output is correct |
53 |
Correct |
1753 ms |
165032 KB |
Output is correct |
54 |
Correct |
1756 ms |
164904 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
1252 KB |
Output is correct |
2 |
Correct |
3 ms |
1252 KB |
Output is correct |
3 |
Correct |
3 ms |
1252 KB |
Output is correct |
4 |
Correct |
3 ms |
1252 KB |
Output is correct |
5 |
Correct |
3 ms |
1312 KB |
Output is correct |
6 |
Correct |
3 ms |
1252 KB |
Output is correct |
7 |
Correct |
3 ms |
1252 KB |
Output is correct |
8 |
Correct |
3 ms |
1252 KB |
Output is correct |
9 |
Correct |
5 ms |
1252 KB |
Output is correct |
10 |
Correct |
3 ms |
1252 KB |
Output is correct |
11 |
Correct |
0 ms |
332 KB |
Output is correct |
12 |
Correct |
1 ms |
332 KB |
Output is correct |
13 |
Correct |
0 ms |
332 KB |
Output is correct |
14 |
Correct |
0 ms |
332 KB |
Output is correct |
15 |
Correct |
0 ms |
332 KB |
Output is correct |
16 |
Correct |
1 ms |
332 KB |
Output is correct |
17 |
Correct |
0 ms |
332 KB |
Output is correct |
18 |
Correct |
1 ms |
332 KB |
Output is correct |
19 |
Correct |
1 ms |
332 KB |
Output is correct |
20 |
Correct |
0 ms |
332 KB |
Output is correct |
21 |
Correct |
5 ms |
1252 KB |
Output is correct |
22 |
Correct |
3 ms |
1252 KB |
Output is correct |
23 |
Correct |
3 ms |
1252 KB |
Output is correct |
24 |
Correct |
3 ms |
1252 KB |
Output is correct |
25 |
Correct |
3 ms |
1252 KB |
Output is correct |
26 |
Correct |
3 ms |
1252 KB |
Output is correct |
27 |
Correct |
4 ms |
1252 KB |
Output is correct |
28 |
Correct |
3 ms |
1252 KB |
Output is correct |
29 |
Correct |
3 ms |
1252 KB |
Output is correct |
30 |
Correct |
3 ms |
1252 KB |
Output is correct |
31 |
Correct |
3 ms |
1252 KB |
Output is correct |
32 |
Correct |
3 ms |
1252 KB |
Output is correct |
33 |
Correct |
1788 ms |
164832 KB |
Output is correct |
34 |
Correct |
1783 ms |
164936 KB |
Output is correct |
35 |
Correct |
1791 ms |
164892 KB |
Output is correct |
36 |
Correct |
1773 ms |
164832 KB |
Output is correct |
37 |
Correct |
1784 ms |
164900 KB |
Output is correct |
38 |
Correct |
1807 ms |
164812 KB |
Output is correct |
39 |
Correct |
1836 ms |
164856 KB |
Output is correct |
40 |
Correct |
1834 ms |
164900 KB |
Output is correct |
41 |
Correct |
1777 ms |
164892 KB |
Output is correct |
42 |
Correct |
1773 ms |
164824 KB |
Output is correct |
43 |
Correct |
1746 ms |
164844 KB |
Output is correct |
44 |
Correct |
1730 ms |
164888 KB |
Output is correct |
45 |
Correct |
1734 ms |
165012 KB |
Output is correct |
46 |
Correct |
1745 ms |
164864 KB |
Output is correct |
47 |
Correct |
1735 ms |
164816 KB |
Output is correct |
48 |
Correct |
1745 ms |
164808 KB |
Output is correct |
49 |
Correct |
1741 ms |
164808 KB |
Output is correct |
50 |
Correct |
1770 ms |
164944 KB |
Output is correct |
51 |
Correct |
1743 ms |
164808 KB |
Output is correct |
52 |
Correct |
1742 ms |
164980 KB |
Output is correct |
53 |
Correct |
1753 ms |
165032 KB |
Output is correct |
54 |
Correct |
1756 ms |
164904 KB |
Output is correct |
55 |
Correct |
1770 ms |
164840 KB |
Output is correct |
56 |
Correct |
1763 ms |
164940 KB |
Output is correct |
57 |
Correct |
1803 ms |
164936 KB |
Output is correct |
58 |
Correct |
1779 ms |
164820 KB |
Output is correct |
59 |
Correct |
1799 ms |
164808 KB |
Output is correct |
60 |
Correct |
1801 ms |
164900 KB |
Output is correct |
61 |
Correct |
1795 ms |
164852 KB |
Output is correct |
62 |
Correct |
1822 ms |
164868 KB |
Output is correct |
63 |
Correct |
1776 ms |
164972 KB |
Output is correct |
64 |
Correct |
1790 ms |
164856 KB |
Output is correct |
65 |
Incorrect |
1789 ms |
164872 KB |
Output isn't correct |
66 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
1252 KB |
Output is correct |
2 |
Correct |
2 ms |
1252 KB |
Output is correct |
3 |
Correct |
3 ms |
1252 KB |
Output is correct |
4 |
Correct |
2 ms |
1252 KB |
Output is correct |
5 |
Correct |
2 ms |
1252 KB |
Output is correct |
6 |
Correct |
2 ms |
1252 KB |
Output is correct |
7 |
Correct |
2 ms |
1252 KB |
Output is correct |
8 |
Correct |
2 ms |
1252 KB |
Output is correct |
9 |
Correct |
4 ms |
1252 KB |
Output is correct |
10 |
Correct |
2 ms |
1252 KB |
Output is correct |
11 |
Correct |
0 ms |
332 KB |
Output is correct |
12 |
Correct |
0 ms |
332 KB |
Output is correct |
13 |
Correct |
0 ms |
332 KB |
Output is correct |
14 |
Correct |
0 ms |
332 KB |
Output is correct |
15 |
Correct |
0 ms |
332 KB |
Output is correct |
16 |
Correct |
3 ms |
1252 KB |
Output is correct |
17 |
Correct |
3 ms |
1252 KB |
Output is correct |
18 |
Correct |
3 ms |
1252 KB |
Output is correct |
19 |
Correct |
3 ms |
1252 KB |
Output is correct |
20 |
Correct |
3 ms |
1312 KB |
Output is correct |
21 |
Correct |
3 ms |
1252 KB |
Output is correct |
22 |
Correct |
3 ms |
1252 KB |
Output is correct |
23 |
Correct |
3 ms |
1252 KB |
Output is correct |
24 |
Correct |
5 ms |
1252 KB |
Output is correct |
25 |
Correct |
3 ms |
1252 KB |
Output is correct |
26 |
Correct |
0 ms |
332 KB |
Output is correct |
27 |
Correct |
1 ms |
332 KB |
Output is correct |
28 |
Correct |
0 ms |
332 KB |
Output is correct |
29 |
Correct |
0 ms |
332 KB |
Output is correct |
30 |
Correct |
0 ms |
332 KB |
Output is correct |
31 |
Correct |
1 ms |
332 KB |
Output is correct |
32 |
Correct |
0 ms |
332 KB |
Output is correct |
33 |
Correct |
1 ms |
332 KB |
Output is correct |
34 |
Correct |
1 ms |
332 KB |
Output is correct |
35 |
Correct |
0 ms |
332 KB |
Output is correct |
36 |
Correct |
5 ms |
1252 KB |
Output is correct |
37 |
Correct |
3 ms |
1252 KB |
Output is correct |
38 |
Correct |
3 ms |
1252 KB |
Output is correct |
39 |
Correct |
3 ms |
1252 KB |
Output is correct |
40 |
Correct |
3 ms |
1252 KB |
Output is correct |
41 |
Correct |
3 ms |
1252 KB |
Output is correct |
42 |
Correct |
4 ms |
1252 KB |
Output is correct |
43 |
Correct |
3 ms |
1252 KB |
Output is correct |
44 |
Correct |
3 ms |
1252 KB |
Output is correct |
45 |
Correct |
3 ms |
1252 KB |
Output is correct |
46 |
Correct |
3 ms |
1252 KB |
Output is correct |
47 |
Correct |
3 ms |
1252 KB |
Output is correct |
48 |
Correct |
1788 ms |
164832 KB |
Output is correct |
49 |
Correct |
1783 ms |
164936 KB |
Output is correct |
50 |
Correct |
1791 ms |
164892 KB |
Output is correct |
51 |
Correct |
1773 ms |
164832 KB |
Output is correct |
52 |
Correct |
1784 ms |
164900 KB |
Output is correct |
53 |
Correct |
1807 ms |
164812 KB |
Output is correct |
54 |
Correct |
1836 ms |
164856 KB |
Output is correct |
55 |
Correct |
1834 ms |
164900 KB |
Output is correct |
56 |
Correct |
1777 ms |
164892 KB |
Output is correct |
57 |
Correct |
1773 ms |
164824 KB |
Output is correct |
58 |
Correct |
1746 ms |
164844 KB |
Output is correct |
59 |
Correct |
1730 ms |
164888 KB |
Output is correct |
60 |
Correct |
1734 ms |
165012 KB |
Output is correct |
61 |
Correct |
1745 ms |
164864 KB |
Output is correct |
62 |
Correct |
1735 ms |
164816 KB |
Output is correct |
63 |
Correct |
1745 ms |
164808 KB |
Output is correct |
64 |
Correct |
1741 ms |
164808 KB |
Output is correct |
65 |
Correct |
1770 ms |
164944 KB |
Output is correct |
66 |
Correct |
1743 ms |
164808 KB |
Output is correct |
67 |
Correct |
1742 ms |
164980 KB |
Output is correct |
68 |
Correct |
1753 ms |
165032 KB |
Output is correct |
69 |
Correct |
1756 ms |
164904 KB |
Output is correct |
70 |
Correct |
1770 ms |
164840 KB |
Output is correct |
71 |
Correct |
1763 ms |
164940 KB |
Output is correct |
72 |
Correct |
1803 ms |
164936 KB |
Output is correct |
73 |
Correct |
1779 ms |
164820 KB |
Output is correct |
74 |
Correct |
1799 ms |
164808 KB |
Output is correct |
75 |
Correct |
1801 ms |
164900 KB |
Output is correct |
76 |
Correct |
1795 ms |
164852 KB |
Output is correct |
77 |
Correct |
1822 ms |
164868 KB |
Output is correct |
78 |
Correct |
1776 ms |
164972 KB |
Output is correct |
79 |
Correct |
1790 ms |
164856 KB |
Output is correct |
80 |
Incorrect |
1789 ms |
164872 KB |
Output isn't correct |
81 |
Halted |
0 ms |
0 KB |
- |