#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ari2 = array<int, 2>;
#define vt vector
#define size(x) (int((x).size()))
#define all(x) begin(x), end(x)
#define REP(a,b,c,d) for(int a=(b);(d)>0?a<=(c):a>=(c);a+=(d))
#define FOR(a,b,c) REP(a,b,c,1)
#define ROF(a,b,c) REP(a,b,c,-1)
constexpr int mxN = 2005;
int N, X[mxN], Y[mxN], W[mxN];
struct Event {
int y, x, i, j;
Event(int _y, int _x, int _i, int _j) : y(_y), x(_x), i(_i), j(_j) {
if (x < 0)
y = -y, x = -x;
}
};
struct Node {
ll ans, lft, rht, sum;
Node operator+(const Node &other) {
return {
max({ans, other.ans, rht + other.lft}),
max(lft, sum + other.lft),
max(other.rht, other.sum + rht),
sum + other.sum
};
}
};
struct ST {
Node st[mxN<<1];
void update(int i, int v) {
st[i+=N] = {max(v, 0), max(v, 0), max(v, 0), v};
for (i >>= 1; i > 0; i >>= 1)
st[i] = st[i<<1] + st[i<<1|1];
}
Node query(int l, int r) {
Node lft = {0, 0, 0, 0};
Node rht = {0, 0, 0, 0};
for (l += N, r += N+1; l < r; l >>= 1, r >>= 1) {
if (l & 1)
lft = lft + st[l++];
if (r & 1)
rht = st[--r] + rht;
}
return lft + rht;
}
} st;
signed main() {
#ifndef DEBUG
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
#endif
cin >> N;
vt<Event> sweep;
FOR(i, 0, N-1)
cin >> X[i] >> Y[i] >> W[i];
FOR(i, 0, N-1)
FOR(j, 0, N-1)
if (i != j && X[i] > X[j])
sweep.push_back(Event(Y[i] - Y[j], X[i] - X[j], i, j));
sort(all(sweep), [&](const Event &a, const Event &b) {
ll va = 1ll * a.y * b.x;
ll vb = 1ll * b.y * a.x;
return va != vb ? va < vb : ari2{-X[a.i], -X[a.j]} < ari2{-X[b.i], -X[b.j]};
});
vt<int> ord(N);
iota(all(ord), 0);
sort(all(ord), [&](const int &a, const int &b) {
return ari2{X[a], Y[a]} < ari2{X[b], Y[b]};
});
vt<int> pos(N);
FOR(ii, 0, N-1) {
const int i = ord[ii];
pos[i] = ii;
st.update(ii, W[i]);
}
ll ans = st.query(0, N-1).ans;
FOR(k, 0, size(sweep)-1) {
auto [y, x, i, j] = sweep[k];
st.update(pos[i], W[j]);
st.update(pos[j], W[i]);
swap(pos[i], pos[j]);
if (k == size(sweep)-1 || 1ll * y * sweep[k+1].x != 1ll * sweep[k+1].y * x)
ans = max(ans, st.query(0, N-1).ans);
}
cout << ans << '\n';
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
604 KB |
Output is correct |
2 |
Correct |
1 ms |
604 KB |
Output is correct |
3 |
Correct |
1 ms |
604 KB |
Output is correct |
4 |
Correct |
1 ms |
604 KB |
Output is correct |
5 |
Correct |
1 ms |
604 KB |
Output is correct |
6 |
Correct |
1 ms |
604 KB |
Output is correct |
7 |
Correct |
1 ms |
684 KB |
Output is correct |
8 |
Correct |
1 ms |
604 KB |
Output is correct |
9 |
Correct |
1 ms |
604 KB |
Output is correct |
10 |
Correct |
1 ms |
604 KB |
Output is correct |
11 |
Correct |
0 ms |
348 KB |
Output is correct |
12 |
Correct |
0 ms |
344 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 |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
600 KB |
Output is correct |
2 |
Correct |
1 ms |
604 KB |
Output is correct |
3 |
Correct |
1 ms |
460 KB |
Output is correct |
4 |
Correct |
2 ms |
604 KB |
Output is correct |
5 |
Correct |
1 ms |
604 KB |
Output is correct |
6 |
Correct |
1 ms |
460 KB |
Output is correct |
7 |
Correct |
1 ms |
604 KB |
Output is correct |
8 |
Correct |
2 ms |
604 KB |
Output is correct |
9 |
Correct |
2 ms |
604 KB |
Output is correct |
10 |
Correct |
1 ms |
604 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 |
352 KB |
Output is correct |
14 |
Correct |
0 ms |
356 KB |
Output is correct |
15 |
Correct |
0 ms |
352 KB |
Output is correct |
16 |
Correct |
0 ms |
408 KB |
Output is correct |
17 |
Correct |
0 ms |
344 KB |
Output is correct |
18 |
Correct |
0 ms |
352 KB |
Output is correct |
19 |
Correct |
0 ms |
348 KB |
Output is correct |
20 |
Correct |
0 ms |
352 KB |
Output is correct |
21 |
Correct |
1 ms |
604 KB |
Output is correct |
22 |
Correct |
1 ms |
604 KB |
Output is correct |
23 |
Correct |
1 ms |
608 KB |
Output is correct |
24 |
Correct |
1 ms |
604 KB |
Output is correct |
25 |
Correct |
1 ms |
464 KB |
Output is correct |
26 |
Correct |
1 ms |
604 KB |
Output is correct |
27 |
Correct |
1 ms |
600 KB |
Output is correct |
28 |
Correct |
1 ms |
604 KB |
Output is correct |
29 |
Correct |
1 ms |
604 KB |
Output is correct |
30 |
Correct |
1 ms |
604 KB |
Output is correct |
31 |
Correct |
2 ms |
856 KB |
Output is correct |
32 |
Correct |
1 ms |
604 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
600 KB |
Output is correct |
2 |
Correct |
1 ms |
604 KB |
Output is correct |
3 |
Correct |
1 ms |
460 KB |
Output is correct |
4 |
Correct |
2 ms |
604 KB |
Output is correct |
5 |
Correct |
1 ms |
604 KB |
Output is correct |
6 |
Correct |
1 ms |
460 KB |
Output is correct |
7 |
Correct |
1 ms |
604 KB |
Output is correct |
8 |
Correct |
2 ms |
604 KB |
Output is correct |
9 |
Correct |
2 ms |
604 KB |
Output is correct |
10 |
Correct |
1 ms |
604 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 |
352 KB |
Output is correct |
14 |
Correct |
0 ms |
356 KB |
Output is correct |
15 |
Correct |
0 ms |
352 KB |
Output is correct |
16 |
Correct |
0 ms |
408 KB |
Output is correct |
17 |
Correct |
0 ms |
344 KB |
Output is correct |
18 |
Correct |
0 ms |
352 KB |
Output is correct |
19 |
Correct |
0 ms |
348 KB |
Output is correct |
20 |
Correct |
0 ms |
352 KB |
Output is correct |
21 |
Correct |
1 ms |
604 KB |
Output is correct |
22 |
Correct |
1 ms |
604 KB |
Output is correct |
23 |
Correct |
1 ms |
608 KB |
Output is correct |
24 |
Correct |
1 ms |
604 KB |
Output is correct |
25 |
Correct |
1 ms |
464 KB |
Output is correct |
26 |
Correct |
1 ms |
604 KB |
Output is correct |
27 |
Correct |
1 ms |
600 KB |
Output is correct |
28 |
Correct |
1 ms |
604 KB |
Output is correct |
29 |
Correct |
1 ms |
604 KB |
Output is correct |
30 |
Correct |
1 ms |
604 KB |
Output is correct |
31 |
Correct |
2 ms |
856 KB |
Output is correct |
32 |
Correct |
1 ms |
604 KB |
Output is correct |
33 |
Correct |
616 ms |
33456 KB |
Output is correct |
34 |
Correct |
592 ms |
33468 KB |
Output is correct |
35 |
Correct |
576 ms |
33480 KB |
Output is correct |
36 |
Correct |
592 ms |
33480 KB |
Output is correct |
37 |
Correct |
601 ms |
33492 KB |
Output is correct |
38 |
Correct |
598 ms |
33472 KB |
Output is correct |
39 |
Correct |
593 ms |
33480 KB |
Output is correct |
40 |
Correct |
577 ms |
33480 KB |
Output is correct |
41 |
Correct |
600 ms |
33480 KB |
Output is correct |
42 |
Correct |
585 ms |
33476 KB |
Output is correct |
43 |
Correct |
600 ms |
33468 KB |
Output is correct |
44 |
Correct |
581 ms |
33468 KB |
Output is correct |
45 |
Correct |
570 ms |
33364 KB |
Output is correct |
46 |
Correct |
616 ms |
33472 KB |
Output is correct |
47 |
Correct |
589 ms |
33472 KB |
Output is correct |
48 |
Correct |
570 ms |
33452 KB |
Output is correct |
49 |
Correct |
569 ms |
33468 KB |
Output is correct |
50 |
Correct |
595 ms |
33476 KB |
Output is correct |
51 |
Correct |
595 ms |
33344 KB |
Output is correct |
52 |
Correct |
598 ms |
33468 KB |
Output is correct |
53 |
Correct |
577 ms |
33476 KB |
Output is correct |
54 |
Correct |
598 ms |
33344 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
600 KB |
Output is correct |
2 |
Correct |
1 ms |
604 KB |
Output is correct |
3 |
Correct |
1 ms |
460 KB |
Output is correct |
4 |
Correct |
2 ms |
604 KB |
Output is correct |
5 |
Correct |
1 ms |
604 KB |
Output is correct |
6 |
Correct |
1 ms |
460 KB |
Output is correct |
7 |
Correct |
1 ms |
604 KB |
Output is correct |
8 |
Correct |
2 ms |
604 KB |
Output is correct |
9 |
Correct |
2 ms |
604 KB |
Output is correct |
10 |
Correct |
1 ms |
604 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 |
352 KB |
Output is correct |
14 |
Correct |
0 ms |
356 KB |
Output is correct |
15 |
Correct |
0 ms |
352 KB |
Output is correct |
16 |
Correct |
0 ms |
408 KB |
Output is correct |
17 |
Correct |
0 ms |
344 KB |
Output is correct |
18 |
Correct |
0 ms |
352 KB |
Output is correct |
19 |
Correct |
0 ms |
348 KB |
Output is correct |
20 |
Correct |
0 ms |
352 KB |
Output is correct |
21 |
Correct |
1 ms |
604 KB |
Output is correct |
22 |
Correct |
1 ms |
604 KB |
Output is correct |
23 |
Correct |
1 ms |
608 KB |
Output is correct |
24 |
Correct |
1 ms |
604 KB |
Output is correct |
25 |
Correct |
1 ms |
464 KB |
Output is correct |
26 |
Correct |
1 ms |
604 KB |
Output is correct |
27 |
Correct |
1 ms |
600 KB |
Output is correct |
28 |
Correct |
1 ms |
604 KB |
Output is correct |
29 |
Correct |
1 ms |
604 KB |
Output is correct |
30 |
Correct |
1 ms |
604 KB |
Output is correct |
31 |
Correct |
2 ms |
856 KB |
Output is correct |
32 |
Correct |
1 ms |
604 KB |
Output is correct |
33 |
Correct |
616 ms |
33456 KB |
Output is correct |
34 |
Correct |
592 ms |
33468 KB |
Output is correct |
35 |
Correct |
576 ms |
33480 KB |
Output is correct |
36 |
Correct |
592 ms |
33480 KB |
Output is correct |
37 |
Correct |
601 ms |
33492 KB |
Output is correct |
38 |
Correct |
598 ms |
33472 KB |
Output is correct |
39 |
Correct |
593 ms |
33480 KB |
Output is correct |
40 |
Correct |
577 ms |
33480 KB |
Output is correct |
41 |
Correct |
600 ms |
33480 KB |
Output is correct |
42 |
Correct |
585 ms |
33476 KB |
Output is correct |
43 |
Correct |
600 ms |
33468 KB |
Output is correct |
44 |
Correct |
581 ms |
33468 KB |
Output is correct |
45 |
Correct |
570 ms |
33364 KB |
Output is correct |
46 |
Correct |
616 ms |
33472 KB |
Output is correct |
47 |
Correct |
589 ms |
33472 KB |
Output is correct |
48 |
Correct |
570 ms |
33452 KB |
Output is correct |
49 |
Correct |
569 ms |
33468 KB |
Output is correct |
50 |
Correct |
595 ms |
33476 KB |
Output is correct |
51 |
Correct |
595 ms |
33344 KB |
Output is correct |
52 |
Correct |
598 ms |
33468 KB |
Output is correct |
53 |
Correct |
577 ms |
33476 KB |
Output is correct |
54 |
Correct |
598 ms |
33344 KB |
Output is correct |
55 |
Correct |
570 ms |
33532 KB |
Output is correct |
56 |
Correct |
606 ms |
33468 KB |
Output is correct |
57 |
Correct |
613 ms |
33476 KB |
Output is correct |
58 |
Correct |
598 ms |
33472 KB |
Output is correct |
59 |
Correct |
595 ms |
33468 KB |
Output is correct |
60 |
Correct |
600 ms |
33472 KB |
Output is correct |
61 |
Correct |
575 ms |
33452 KB |
Output is correct |
62 |
Correct |
619 ms |
33468 KB |
Output is correct |
63 |
Correct |
592 ms |
33468 KB |
Output is correct |
64 |
Correct |
602 ms |
33480 KB |
Output is correct |
65 |
Correct |
598 ms |
33472 KB |
Output is correct |
66 |
Correct |
603 ms |
33452 KB |
Output is correct |
67 |
Correct |
588 ms |
33468 KB |
Output is correct |
68 |
Correct |
612 ms |
33472 KB |
Output is correct |
69 |
Correct |
602 ms |
33468 KB |
Output is correct |
70 |
Correct |
579 ms |
33480 KB |
Output is correct |
71 |
Correct |
585 ms |
33448 KB |
Output is correct |
72 |
Correct |
617 ms |
33468 KB |
Output is correct |
73 |
Correct |
597 ms |
33476 KB |
Output is correct |
74 |
Correct |
595 ms |
33472 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
604 KB |
Output is correct |
2 |
Correct |
1 ms |
604 KB |
Output is correct |
3 |
Correct |
1 ms |
604 KB |
Output is correct |
4 |
Correct |
1 ms |
604 KB |
Output is correct |
5 |
Correct |
1 ms |
604 KB |
Output is correct |
6 |
Correct |
1 ms |
604 KB |
Output is correct |
7 |
Correct |
1 ms |
684 KB |
Output is correct |
8 |
Correct |
1 ms |
604 KB |
Output is correct |
9 |
Correct |
1 ms |
604 KB |
Output is correct |
10 |
Correct |
1 ms |
604 KB |
Output is correct |
11 |
Correct |
0 ms |
348 KB |
Output is correct |
12 |
Correct |
0 ms |
344 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 |
2 ms |
600 KB |
Output is correct |
17 |
Correct |
1 ms |
604 KB |
Output is correct |
18 |
Correct |
1 ms |
460 KB |
Output is correct |
19 |
Correct |
2 ms |
604 KB |
Output is correct |
20 |
Correct |
1 ms |
604 KB |
Output is correct |
21 |
Correct |
1 ms |
460 KB |
Output is correct |
22 |
Correct |
1 ms |
604 KB |
Output is correct |
23 |
Correct |
2 ms |
604 KB |
Output is correct |
24 |
Correct |
2 ms |
604 KB |
Output is correct |
25 |
Correct |
1 ms |
604 KB |
Output is correct |
26 |
Correct |
0 ms |
348 KB |
Output is correct |
27 |
Correct |
0 ms |
348 KB |
Output is correct |
28 |
Correct |
0 ms |
352 KB |
Output is correct |
29 |
Correct |
0 ms |
356 KB |
Output is correct |
30 |
Correct |
0 ms |
352 KB |
Output is correct |
31 |
Correct |
0 ms |
408 KB |
Output is correct |
32 |
Correct |
0 ms |
344 KB |
Output is correct |
33 |
Correct |
0 ms |
352 KB |
Output is correct |
34 |
Correct |
0 ms |
348 KB |
Output is correct |
35 |
Correct |
0 ms |
352 KB |
Output is correct |
36 |
Correct |
1 ms |
604 KB |
Output is correct |
37 |
Correct |
1 ms |
604 KB |
Output is correct |
38 |
Correct |
1 ms |
608 KB |
Output is correct |
39 |
Correct |
1 ms |
604 KB |
Output is correct |
40 |
Correct |
1 ms |
464 KB |
Output is correct |
41 |
Correct |
1 ms |
604 KB |
Output is correct |
42 |
Correct |
1 ms |
600 KB |
Output is correct |
43 |
Correct |
1 ms |
604 KB |
Output is correct |
44 |
Correct |
1 ms |
604 KB |
Output is correct |
45 |
Correct |
1 ms |
604 KB |
Output is correct |
46 |
Correct |
2 ms |
856 KB |
Output is correct |
47 |
Correct |
1 ms |
604 KB |
Output is correct |
48 |
Correct |
616 ms |
33456 KB |
Output is correct |
49 |
Correct |
592 ms |
33468 KB |
Output is correct |
50 |
Correct |
576 ms |
33480 KB |
Output is correct |
51 |
Correct |
592 ms |
33480 KB |
Output is correct |
52 |
Correct |
601 ms |
33492 KB |
Output is correct |
53 |
Correct |
598 ms |
33472 KB |
Output is correct |
54 |
Correct |
593 ms |
33480 KB |
Output is correct |
55 |
Correct |
577 ms |
33480 KB |
Output is correct |
56 |
Correct |
600 ms |
33480 KB |
Output is correct |
57 |
Correct |
585 ms |
33476 KB |
Output is correct |
58 |
Correct |
600 ms |
33468 KB |
Output is correct |
59 |
Correct |
581 ms |
33468 KB |
Output is correct |
60 |
Correct |
570 ms |
33364 KB |
Output is correct |
61 |
Correct |
616 ms |
33472 KB |
Output is correct |
62 |
Correct |
589 ms |
33472 KB |
Output is correct |
63 |
Correct |
570 ms |
33452 KB |
Output is correct |
64 |
Correct |
569 ms |
33468 KB |
Output is correct |
65 |
Correct |
595 ms |
33476 KB |
Output is correct |
66 |
Correct |
595 ms |
33344 KB |
Output is correct |
67 |
Correct |
598 ms |
33468 KB |
Output is correct |
68 |
Correct |
577 ms |
33476 KB |
Output is correct |
69 |
Correct |
598 ms |
33344 KB |
Output is correct |
70 |
Correct |
570 ms |
33532 KB |
Output is correct |
71 |
Correct |
606 ms |
33468 KB |
Output is correct |
72 |
Correct |
613 ms |
33476 KB |
Output is correct |
73 |
Correct |
598 ms |
33472 KB |
Output is correct |
74 |
Correct |
595 ms |
33468 KB |
Output is correct |
75 |
Correct |
600 ms |
33472 KB |
Output is correct |
76 |
Correct |
575 ms |
33452 KB |
Output is correct |
77 |
Correct |
619 ms |
33468 KB |
Output is correct |
78 |
Correct |
592 ms |
33468 KB |
Output is correct |
79 |
Correct |
602 ms |
33480 KB |
Output is correct |
80 |
Correct |
598 ms |
33472 KB |
Output is correct |
81 |
Correct |
603 ms |
33452 KB |
Output is correct |
82 |
Correct |
588 ms |
33468 KB |
Output is correct |
83 |
Correct |
612 ms |
33472 KB |
Output is correct |
84 |
Correct |
602 ms |
33468 KB |
Output is correct |
85 |
Correct |
579 ms |
33480 KB |
Output is correct |
86 |
Correct |
585 ms |
33448 KB |
Output is correct |
87 |
Correct |
617 ms |
33468 KB |
Output is correct |
88 |
Correct |
597 ms |
33476 KB |
Output is correct |
89 |
Correct |
595 ms |
33472 KB |
Output is correct |
90 |
Correct |
596 ms |
33468 KB |
Output is correct |
91 |
Correct |
603 ms |
33476 KB |
Output is correct |
92 |
Correct |
598 ms |
33412 KB |
Output is correct |
93 |
Correct |
591 ms |
33480 KB |
Output is correct |
94 |
Correct |
603 ms |
33480 KB |
Output is correct |
95 |
Correct |
612 ms |
33476 KB |
Output is correct |
96 |
Correct |
600 ms |
33492 KB |
Output is correct |
97 |
Correct |
587 ms |
33468 KB |
Output is correct |
98 |
Correct |
600 ms |
33476 KB |
Output is correct |
99 |
Correct |
611 ms |
33480 KB |
Output is correct |
100 |
Correct |
288 ms |
17100 KB |
Output is correct |
101 |
Correct |
284 ms |
17096 KB |
Output is correct |
102 |
Correct |
300 ms |
17100 KB |
Output is correct |
103 |
Correct |
287 ms |
17100 KB |
Output is correct |
104 |
Correct |
285 ms |
17100 KB |
Output is correct |
105 |
Correct |
404 ms |
33472 KB |
Output is correct |
106 |
Correct |
386 ms |
33476 KB |
Output is correct |
107 |
Correct |
391 ms |
33476 KB |
Output is correct |
108 |
Correct |
397 ms |
33480 KB |
Output is correct |
109 |
Correct |
404 ms |
33476 KB |
Output is correct |
110 |
Correct |
533 ms |
33480 KB |
Output is correct |
111 |
Correct |
560 ms |
33480 KB |
Output is correct |
112 |
Correct |
556 ms |
33480 KB |
Output is correct |
113 |
Correct |
571 ms |
33468 KB |
Output is correct |
114 |
Correct |
542 ms |
33472 KB |
Output is correct |
115 |
Correct |
555 ms |
33464 KB |
Output is correct |
116 |
Correct |
562 ms |
33480 KB |
Output is correct |
117 |
Correct |
546 ms |
33448 KB |
Output is correct |
118 |
Correct |
561 ms |
33464 KB |
Output is correct |
119 |
Correct |
559 ms |
33468 KB |
Output is correct |
120 |
Correct |
0 ms |
344 KB |
Output is correct |
121 |
Correct |
0 ms |
600 KB |
Output is correct |
122 |
Correct |
585 ms |
33392 KB |
Output is correct |
123 |
Correct |
584 ms |
33468 KB |
Output is correct |
124 |
Correct |
617 ms |
33480 KB |
Output is correct |
125 |
Correct |
588 ms |
33480 KB |
Output is correct |
126 |
Correct |
584 ms |
33316 KB |
Output is correct |
127 |
Correct |
580 ms |
33360 KB |
Output is correct |
128 |
Correct |
584 ms |
33472 KB |
Output is correct |
129 |
Correct |
581 ms |
33472 KB |
Output is correct |
130 |
Correct |
604 ms |
33480 KB |
Output is correct |
131 |
Correct |
568 ms |
33468 KB |
Output is correct |
132 |
Correct |
612 ms |
33476 KB |
Output is correct |
133 |
Correct |
579 ms |
33480 KB |
Output is correct |