#include <bits/stdc++.h>
using namespace std;
struct point {
int x;
int y;
int w;
bool operator < (point p) {
if(x == p.x) return y > p.y;
return x < p.x;
}
};
struct frac {
int p;
int q;
frac() { }
frac(int _p, int _q) { p = _p; q = _q; }
};
struct node {
long long mx;
long long pref;
long long suff;
long long sum;
};
bool operator < (frac a, frac b) {
return a.p * 1LL * b.q < b.p * 1LL * a.q;
}
const int N = 2010;
int n;
point a[N];
map<frac, vector<pair<int, int>>> buc;
vector<frac> slopes;
int order[N], pos[N];
node st[4 * N];
void update(int index, int l, int r, int x, int val) {
if(l > r || r < x || x < l) return;
if(l == r) {
st[index].mx = st[index].pref = st[index].suff = max(val, 0);
st[index].sum = val;
return;
}
int mid = (l + r) / 2;
update(2 * index, l, mid, x, val);
update(2 * index + 1, mid + 1, r, x, val);
st[index].mx = max({st[2 * index].mx, st[2 * index + 1].mx, st[2 * index].suff + st[2 * index + 1].pref});
st[index].pref = max(st[2 * index].pref, st[2 * index].sum + st[2 * index + 1].pref);
st[index].suff = max(st[2 * index + 1].suff, st[2 * index + 1].sum + st[2 * index].suff);
st[index].sum = st[2 * index].sum + st[2 * index + 1].sum;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> n;
for(int i = 1; i <= n; i++) cin >> a[i].x >> a[i].y >> a[i].w;
for(int i = 1; i <= n; i++) {
for(int j = i + 1; j <= n; j++) {
int sign = 1;
int dx = a[i].x - a[j].x, dy = a[i].y - a[j].y;
if(dx < 0) sign *= -1;
if(dy < 0) sign *= -1;
dx = abs(dx);
dy = abs(dy);
int g = __gcd(dx, dy);
dx /= g;
dy /= g;
if(dx != 0) dy *= sign;
if(a[i] < a[j]) buc[frac(dy, dx)].emplace_back(i, j);
else buc[frac(dy, dx)].emplace_back(j, i);
slopes.push_back(frac(dy, dx));
}
}
sort(slopes.begin(), slopes.end(), [&](frac a, frac b) {
return a.p * 1LL * b.q < b.p * 1LL * a.q;
});
for(int i = 1; i <= n; i++) order[i] = i;
sort(order + 1, order + n + 1, [&](int i, int j) {
return a[i] < a[j];
});
for(int i = 1; i <= n; i++) pos[order[i]] = i;
for(int i = 1; i <= n; i++) update(1, 1, n, i, a[order[i]].w);
long long ans = 0;
for(frac slope : slopes) {
ans = max(ans, st[1].mx);
sort(buc[slope].begin(), buc[slope].end(), [&](pair<int, int> i, pair<int, int> j) {
if(i.first == j.first) return a[i.second] < a[j.second];
return a[i.first] < a[j.first];
});
for(pair<int, int> p : buc[slope]) {
int i = p.first, j = p.second;
if(pos[i] < pos[j]) {
update(1, 1, n, pos[i], a[order[pos[j]]].w);
update(1, 1, n, pos[j], a[order[pos[i]]].w);
swap(order[pos[i]], order[pos[j]]);
swap(pos[i], pos[j]);
}
}
}
ans = max(ans, st[1].mx);
cout << ans;
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
581 ms |
604 KB |
Output is correct |
2 |
Correct |
580 ms |
636 KB |
Output is correct |
3 |
Correct |
580 ms |
628 KB |
Output is correct |
4 |
Correct |
592 ms |
636 KB |
Output is correct |
5 |
Correct |
579 ms |
632 KB |
Output is correct |
6 |
Correct |
581 ms |
640 KB |
Output is correct |
7 |
Correct |
584 ms |
636 KB |
Output is correct |
8 |
Correct |
606 ms |
636 KB |
Output is correct |
9 |
Correct |
576 ms |
600 KB |
Output is correct |
10 |
Correct |
586 ms |
640 KB |
Output is correct |
11 |
Correct |
0 ms |
348 KB |
Output is correct |
12 |
Correct |
0 ms |
348 KB |
Output is correct |
13 |
Correct |
0 ms |
344 KB |
Output is correct |
14 |
Correct |
1 ms |
348 KB |
Output is correct |
15 |
Correct |
0 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
1116 KB |
Output is correct |
2 |
Correct |
4 ms |
860 KB |
Output is correct |
3 |
Correct |
4 ms |
860 KB |
Output is correct |
4 |
Correct |
4 ms |
860 KB |
Output is correct |
5 |
Correct |
4 ms |
860 KB |
Output is correct |
6 |
Correct |
4 ms |
860 KB |
Output is correct |
7 |
Correct |
4 ms |
860 KB |
Output is correct |
8 |
Correct |
4 ms |
860 KB |
Output is correct |
9 |
Correct |
4 ms |
860 KB |
Output is correct |
10 |
Correct |
4 ms |
1052 KB |
Output is correct |
11 |
Correct |
0 ms |
344 KB |
Output is correct |
12 |
Correct |
0 ms |
348 KB |
Output is correct |
13 |
Correct |
0 ms |
348 KB |
Output is correct |
14 |
Correct |
0 ms |
348 KB |
Output is correct |
15 |
Correct |
0 ms |
348 KB |
Output is correct |
16 |
Correct |
1 ms |
348 KB |
Output is correct |
17 |
Correct |
1 ms |
348 KB |
Output is correct |
18 |
Correct |
0 ms |
348 KB |
Output is correct |
19 |
Correct |
0 ms |
348 KB |
Output is correct |
20 |
Correct |
0 ms |
348 KB |
Output is correct |
21 |
Correct |
4 ms |
860 KB |
Output is correct |
22 |
Correct |
4 ms |
860 KB |
Output is correct |
23 |
Correct |
4 ms |
860 KB |
Output is correct |
24 |
Correct |
4 ms |
1112 KB |
Output is correct |
25 |
Correct |
4 ms |
860 KB |
Output is correct |
26 |
Correct |
4 ms |
860 KB |
Output is correct |
27 |
Correct |
3 ms |
860 KB |
Output is correct |
28 |
Correct |
4 ms |
856 KB |
Output is correct |
29 |
Correct |
4 ms |
860 KB |
Output is correct |
30 |
Correct |
4 ms |
860 KB |
Output is correct |
31 |
Correct |
4 ms |
856 KB |
Output is correct |
32 |
Correct |
4 ms |
860 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
1116 KB |
Output is correct |
2 |
Correct |
4 ms |
860 KB |
Output is correct |
3 |
Correct |
4 ms |
860 KB |
Output is correct |
4 |
Correct |
4 ms |
860 KB |
Output is correct |
5 |
Correct |
4 ms |
860 KB |
Output is correct |
6 |
Correct |
4 ms |
860 KB |
Output is correct |
7 |
Correct |
4 ms |
860 KB |
Output is correct |
8 |
Correct |
4 ms |
860 KB |
Output is correct |
9 |
Correct |
4 ms |
860 KB |
Output is correct |
10 |
Correct |
4 ms |
1052 KB |
Output is correct |
11 |
Correct |
0 ms |
344 KB |
Output is correct |
12 |
Correct |
0 ms |
348 KB |
Output is correct |
13 |
Correct |
0 ms |
348 KB |
Output is correct |
14 |
Correct |
0 ms |
348 KB |
Output is correct |
15 |
Correct |
0 ms |
348 KB |
Output is correct |
16 |
Correct |
1 ms |
348 KB |
Output is correct |
17 |
Correct |
1 ms |
348 KB |
Output is correct |
18 |
Correct |
0 ms |
348 KB |
Output is correct |
19 |
Correct |
0 ms |
348 KB |
Output is correct |
20 |
Correct |
0 ms |
348 KB |
Output is correct |
21 |
Correct |
4 ms |
860 KB |
Output is correct |
22 |
Correct |
4 ms |
860 KB |
Output is correct |
23 |
Correct |
4 ms |
860 KB |
Output is correct |
24 |
Correct |
4 ms |
1112 KB |
Output is correct |
25 |
Correct |
4 ms |
860 KB |
Output is correct |
26 |
Correct |
4 ms |
860 KB |
Output is correct |
27 |
Correct |
3 ms |
860 KB |
Output is correct |
28 |
Correct |
4 ms |
856 KB |
Output is correct |
29 |
Correct |
4 ms |
860 KB |
Output is correct |
30 |
Correct |
4 ms |
860 KB |
Output is correct |
31 |
Correct |
4 ms |
856 KB |
Output is correct |
32 |
Correct |
4 ms |
860 KB |
Output is correct |
33 |
Execution timed out |
2087 ms |
197708 KB |
Time limit exceeded |
34 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
1116 KB |
Output is correct |
2 |
Correct |
4 ms |
860 KB |
Output is correct |
3 |
Correct |
4 ms |
860 KB |
Output is correct |
4 |
Correct |
4 ms |
860 KB |
Output is correct |
5 |
Correct |
4 ms |
860 KB |
Output is correct |
6 |
Correct |
4 ms |
860 KB |
Output is correct |
7 |
Correct |
4 ms |
860 KB |
Output is correct |
8 |
Correct |
4 ms |
860 KB |
Output is correct |
9 |
Correct |
4 ms |
860 KB |
Output is correct |
10 |
Correct |
4 ms |
1052 KB |
Output is correct |
11 |
Correct |
0 ms |
344 KB |
Output is correct |
12 |
Correct |
0 ms |
348 KB |
Output is correct |
13 |
Correct |
0 ms |
348 KB |
Output is correct |
14 |
Correct |
0 ms |
348 KB |
Output is correct |
15 |
Correct |
0 ms |
348 KB |
Output is correct |
16 |
Correct |
1 ms |
348 KB |
Output is correct |
17 |
Correct |
1 ms |
348 KB |
Output is correct |
18 |
Correct |
0 ms |
348 KB |
Output is correct |
19 |
Correct |
0 ms |
348 KB |
Output is correct |
20 |
Correct |
0 ms |
348 KB |
Output is correct |
21 |
Correct |
4 ms |
860 KB |
Output is correct |
22 |
Correct |
4 ms |
860 KB |
Output is correct |
23 |
Correct |
4 ms |
860 KB |
Output is correct |
24 |
Correct |
4 ms |
1112 KB |
Output is correct |
25 |
Correct |
4 ms |
860 KB |
Output is correct |
26 |
Correct |
4 ms |
860 KB |
Output is correct |
27 |
Correct |
3 ms |
860 KB |
Output is correct |
28 |
Correct |
4 ms |
856 KB |
Output is correct |
29 |
Correct |
4 ms |
860 KB |
Output is correct |
30 |
Correct |
4 ms |
860 KB |
Output is correct |
31 |
Correct |
4 ms |
856 KB |
Output is correct |
32 |
Correct |
4 ms |
860 KB |
Output is correct |
33 |
Execution timed out |
2087 ms |
197708 KB |
Time limit exceeded |
34 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
581 ms |
604 KB |
Output is correct |
2 |
Correct |
580 ms |
636 KB |
Output is correct |
3 |
Correct |
580 ms |
628 KB |
Output is correct |
4 |
Correct |
592 ms |
636 KB |
Output is correct |
5 |
Correct |
579 ms |
632 KB |
Output is correct |
6 |
Correct |
581 ms |
640 KB |
Output is correct |
7 |
Correct |
584 ms |
636 KB |
Output is correct |
8 |
Correct |
606 ms |
636 KB |
Output is correct |
9 |
Correct |
576 ms |
600 KB |
Output is correct |
10 |
Correct |
586 ms |
640 KB |
Output is correct |
11 |
Correct |
0 ms |
348 KB |
Output is correct |
12 |
Correct |
0 ms |
348 KB |
Output is correct |
13 |
Correct |
0 ms |
344 KB |
Output is correct |
14 |
Correct |
1 ms |
348 KB |
Output is correct |
15 |
Correct |
0 ms |
348 KB |
Output is correct |
16 |
Correct |
4 ms |
1116 KB |
Output is correct |
17 |
Correct |
4 ms |
860 KB |
Output is correct |
18 |
Correct |
4 ms |
860 KB |
Output is correct |
19 |
Correct |
4 ms |
860 KB |
Output is correct |
20 |
Correct |
4 ms |
860 KB |
Output is correct |
21 |
Correct |
4 ms |
860 KB |
Output is correct |
22 |
Correct |
4 ms |
860 KB |
Output is correct |
23 |
Correct |
4 ms |
860 KB |
Output is correct |
24 |
Correct |
4 ms |
860 KB |
Output is correct |
25 |
Correct |
4 ms |
1052 KB |
Output is correct |
26 |
Correct |
0 ms |
344 KB |
Output is correct |
27 |
Correct |
0 ms |
348 KB |
Output is correct |
28 |
Correct |
0 ms |
348 KB |
Output is correct |
29 |
Correct |
0 ms |
348 KB |
Output is correct |
30 |
Correct |
0 ms |
348 KB |
Output is correct |
31 |
Correct |
1 ms |
348 KB |
Output is correct |
32 |
Correct |
1 ms |
348 KB |
Output is correct |
33 |
Correct |
0 ms |
348 KB |
Output is correct |
34 |
Correct |
0 ms |
348 KB |
Output is correct |
35 |
Correct |
0 ms |
348 KB |
Output is correct |
36 |
Correct |
4 ms |
860 KB |
Output is correct |
37 |
Correct |
4 ms |
860 KB |
Output is correct |
38 |
Correct |
4 ms |
860 KB |
Output is correct |
39 |
Correct |
4 ms |
1112 KB |
Output is correct |
40 |
Correct |
4 ms |
860 KB |
Output is correct |
41 |
Correct |
4 ms |
860 KB |
Output is correct |
42 |
Correct |
3 ms |
860 KB |
Output is correct |
43 |
Correct |
4 ms |
856 KB |
Output is correct |
44 |
Correct |
4 ms |
860 KB |
Output is correct |
45 |
Correct |
4 ms |
860 KB |
Output is correct |
46 |
Correct |
4 ms |
856 KB |
Output is correct |
47 |
Correct |
4 ms |
860 KB |
Output is correct |
48 |
Execution timed out |
2087 ms |
197708 KB |
Time limit exceeded |
49 |
Halted |
0 ms |
0 KB |
- |