#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 4e5+ 5, MOD = 998244353;
int n,pos[N],t[N];
ll x[N],y[N],w[N];
vector<array<ll,3>> a;
struct node{
ll res,mxl,mxr,sum;
};
node T[N * 4];
node merge(node l,node r){
node ret;
ret.sum = l.sum + r.sum;
ret.res = max({l.res,r.res});
ret.res = max(ret.res,l.mxr + r.mxl);
ret.mxr = max(r.mxr,r.sum + l.mxr);
ret.mxl = max(l.mxl,l.sum + r.mxl);
return ret;
}
void upd(int pos,ll val,int v = 1,int tl = 1,int tr = n){
if(tl == tr){
T[v].sum = val;
T[v].res = T[v].mxr = T[v].mxl = max(0ll,val);
}else{
int tm = (tl + tr) >> 1;
if(pos <= tm) upd(pos,val,v+v,tl,tm);
else upd(pos,val,v+v+1,tm+1,tr);
T[v] = merge(T[v+v],T[v+v+1]);
}
}
void out(int v = 1,int tl = 1,int tr = n){
if(tl == tr){
cout << tl << ' ' << T[v].sum << '\n';
}else{
int tm = (tl + tr) >> 1;
out(v+v,tl,tm);
out(v+v+1,tm+1,tr);
}
}
void test() {
cin >> n;
for(int i = 1;i <= n;i++){
cin >> x[i] >> y[i] >> w[i];
a.push_back({x[i],-y[i],i});
}
if(n == 1){
cout << max(0ll,w[1]) << '\n';
return;
}
sort(a.begin(),a.end());
for(int i = 0;i < (int)a.size();i++){
pos[a[i][2]] = i + 1;
t[i + 1] = a[i][2];
upd(i+1,w[a[i][2]]);
}
vector<pair<long double,pair<int,int>>> cur;
for(int i = 1;i <= n;i++){
for(int j = i+1;j <= n;j++){
long double val = (long double)(y[j]-y[i]) / (long double)(x[j] - x[i]);
cur.push_back({val,{i,j}});
}
}
ll res = 0;
sort(cur.rbegin(),cur.rend());
for(int i = 0;i < (int)cur.size();i++){
vector<pair<int,int>> ss,s1;
for(int j = i;j <= (int)cur.size();j++){
if(j == (int)cur.size() || cur[j].first != cur[i].first){
i = j - 1;
break;
}
int L = min(pos[cur[j].second.first], pos[cur[j].second.second]), R = max(pos[cur[j].second.first],
pos[cur[j].second.second]);
ss.push_back({L,R});
}
vector<ll> sums;
sort(ss.begin(),ss.end());
ll mn = 0,curs = 0;
ll max_checked;
for(int j = 0;j < (int)ss.size();j++) {
if (j && max_checked >= ss[j].second) continue;
int mx = ss[j].second;
for (int k = j; k <= (int) ss.size(); k++) {
if (k == (int) ss.size() || ss[k].first != ss[j].first) {
j = k - 1;
break;
}
max_checked = ss[k].second;
mx = ss[k].second;
}
int l = ss[j].first, r = mx;
s1.push_back({l, r});
while (l < r) {
swap(t[l], t[r]);
upd(l, w[t[l]]);
upd(r, w[t[r]]);
pos[t[l]] = l;
pos[t[r]] = r;
l++;
r--;
}
}
// cout << T[1].res << "x\n";
// cout << '\n';
// for(int j = 1;j <= n;j++){
// cout << j << ' ' << w[t[j]] << '\n';
// }
// cout << '\n';
// for(auto [L,R]:s1){
// ll f = w[t[L]];
// for(int j = L + 1;j <= R;j++){
// upd(j,0);
// f += w[t[j]];
// }
// upd(L,f);
// }
res = max(res,T[1].res);
// for(auto [L,R]:s1){
// for(int j = L;j <= R;j++){
// upd(j,w[t[j]]);
// }
// }
}
cout << res << '\n';
}
signed main(){
ios_base::sync_with_stdio(false);cin.tie(0);
int T = 1;
// cin >> T;
while(T--){
test();
}
}
Compilation message
bulldozer.cpp: In function 'void test()':
bulldozer.cpp:83:12: warning: unused variable 'mn' [-Wunused-variable]
83 | ll mn = 0,curs = 0;
| ^~
bulldozer.cpp:83:19: warning: unused variable 'curs' [-Wunused-variable]
83 | ll mn = 0,curs = 0;
| ^~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
11096 KB |
Output is correct |
2 |
Correct |
2 ms |
10972 KB |
Output is correct |
3 |
Correct |
2 ms |
11096 KB |
Output is correct |
4 |
Correct |
3 ms |
11100 KB |
Output is correct |
5 |
Correct |
2 ms |
11100 KB |
Output is correct |
6 |
Correct |
2 ms |
11096 KB |
Output is correct |
7 |
Correct |
3 ms |
11096 KB |
Output is correct |
8 |
Correct |
3 ms |
11100 KB |
Output is correct |
9 |
Correct |
2 ms |
11100 KB |
Output is correct |
10 |
Correct |
2 ms |
11100 KB |
Output is correct |
11 |
Correct |
1 ms |
6488 KB |
Output is correct |
12 |
Correct |
1 ms |
6492 KB |
Output is correct |
13 |
Correct |
2 ms |
10588 KB |
Output is correct |
14 |
Correct |
2 ms |
10712 KB |
Output is correct |
15 |
Correct |
2 ms |
10588 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
11100 KB |
Output is correct |
2 |
Correct |
3 ms |
11096 KB |
Output is correct |
3 |
Correct |
3 ms |
11100 KB |
Output is correct |
4 |
Correct |
4 ms |
11100 KB |
Output is correct |
5 |
Correct |
4 ms |
11100 KB |
Output is correct |
6 |
Correct |
3 ms |
11100 KB |
Output is correct |
7 |
Correct |
4 ms |
11100 KB |
Output is correct |
8 |
Correct |
4 ms |
11100 KB |
Output is correct |
9 |
Correct |
4 ms |
11100 KB |
Output is correct |
10 |
Correct |
4 ms |
11096 KB |
Output is correct |
11 |
Correct |
2 ms |
6744 KB |
Output is correct |
12 |
Correct |
1 ms |
6492 KB |
Output is correct |
13 |
Correct |
2 ms |
10716 KB |
Output is correct |
14 |
Correct |
2 ms |
10704 KB |
Output is correct |
15 |
Correct |
2 ms |
10788 KB |
Output is correct |
16 |
Correct |
2 ms |
10588 KB |
Output is correct |
17 |
Correct |
1 ms |
10588 KB |
Output is correct |
18 |
Correct |
2 ms |
10588 KB |
Output is correct |
19 |
Correct |
2 ms |
10700 KB |
Output is correct |
20 |
Correct |
2 ms |
10588 KB |
Output is correct |
21 |
Correct |
3 ms |
11100 KB |
Output is correct |
22 |
Correct |
3 ms |
11100 KB |
Output is correct |
23 |
Correct |
4 ms |
11100 KB |
Output is correct |
24 |
Correct |
3 ms |
11100 KB |
Output is correct |
25 |
Correct |
4 ms |
11100 KB |
Output is correct |
26 |
Correct |
3 ms |
10972 KB |
Output is correct |
27 |
Correct |
3 ms |
11352 KB |
Output is correct |
28 |
Correct |
4 ms |
11100 KB |
Output is correct |
29 |
Correct |
4 ms |
10964 KB |
Output is correct |
30 |
Correct |
3 ms |
11100 KB |
Output is correct |
31 |
Correct |
3 ms |
11100 KB |
Output is correct |
32 |
Correct |
4 ms |
11100 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
11100 KB |
Output is correct |
2 |
Correct |
3 ms |
11096 KB |
Output is correct |
3 |
Correct |
3 ms |
11100 KB |
Output is correct |
4 |
Correct |
4 ms |
11100 KB |
Output is correct |
5 |
Correct |
4 ms |
11100 KB |
Output is correct |
6 |
Correct |
3 ms |
11100 KB |
Output is correct |
7 |
Correct |
4 ms |
11100 KB |
Output is correct |
8 |
Correct |
4 ms |
11100 KB |
Output is correct |
9 |
Correct |
4 ms |
11100 KB |
Output is correct |
10 |
Correct |
4 ms |
11096 KB |
Output is correct |
11 |
Correct |
2 ms |
6744 KB |
Output is correct |
12 |
Correct |
1 ms |
6492 KB |
Output is correct |
13 |
Correct |
2 ms |
10716 KB |
Output is correct |
14 |
Correct |
2 ms |
10704 KB |
Output is correct |
15 |
Correct |
2 ms |
10788 KB |
Output is correct |
16 |
Correct |
2 ms |
10588 KB |
Output is correct |
17 |
Correct |
1 ms |
10588 KB |
Output is correct |
18 |
Correct |
2 ms |
10588 KB |
Output is correct |
19 |
Correct |
2 ms |
10700 KB |
Output is correct |
20 |
Correct |
2 ms |
10588 KB |
Output is correct |
21 |
Correct |
3 ms |
11100 KB |
Output is correct |
22 |
Correct |
3 ms |
11100 KB |
Output is correct |
23 |
Correct |
4 ms |
11100 KB |
Output is correct |
24 |
Correct |
3 ms |
11100 KB |
Output is correct |
25 |
Correct |
4 ms |
11100 KB |
Output is correct |
26 |
Correct |
3 ms |
10972 KB |
Output is correct |
27 |
Correct |
3 ms |
11352 KB |
Output is correct |
28 |
Correct |
4 ms |
11100 KB |
Output is correct |
29 |
Correct |
4 ms |
10964 KB |
Output is correct |
30 |
Correct |
3 ms |
11100 KB |
Output is correct |
31 |
Correct |
3 ms |
11100 KB |
Output is correct |
32 |
Correct |
4 ms |
11100 KB |
Output is correct |
33 |
Correct |
1211 ms |
77140 KB |
Output is correct |
34 |
Correct |
1234 ms |
77120 KB |
Output is correct |
35 |
Correct |
1212 ms |
77988 KB |
Output is correct |
36 |
Correct |
1201 ms |
78524 KB |
Output is correct |
37 |
Correct |
1226 ms |
77220 KB |
Output is correct |
38 |
Correct |
1214 ms |
76976 KB |
Output is correct |
39 |
Correct |
1199 ms |
76708 KB |
Output is correct |
40 |
Correct |
1234 ms |
77256 KB |
Output is correct |
41 |
Correct |
1212 ms |
76960 KB |
Output is correct |
42 |
Correct |
1191 ms |
76984 KB |
Output is correct |
43 |
Correct |
1194 ms |
78140 KB |
Output is correct |
44 |
Correct |
1186 ms |
77220 KB |
Output is correct |
45 |
Correct |
1180 ms |
78020 KB |
Output is correct |
46 |
Correct |
1207 ms |
77244 KB |
Output is correct |
47 |
Correct |
1224 ms |
77736 KB |
Output is correct |
48 |
Correct |
1183 ms |
77984 KB |
Output is correct |
49 |
Correct |
1183 ms |
77744 KB |
Output is correct |
50 |
Correct |
1237 ms |
78012 KB |
Output is correct |
51 |
Correct |
1190 ms |
77984 KB |
Output is correct |
52 |
Correct |
1186 ms |
78256 KB |
Output is correct |
53 |
Correct |
1197 ms |
78492 KB |
Output is correct |
54 |
Correct |
1226 ms |
77484 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
11100 KB |
Output is correct |
2 |
Correct |
3 ms |
11096 KB |
Output is correct |
3 |
Correct |
3 ms |
11100 KB |
Output is correct |
4 |
Correct |
4 ms |
11100 KB |
Output is correct |
5 |
Correct |
4 ms |
11100 KB |
Output is correct |
6 |
Correct |
3 ms |
11100 KB |
Output is correct |
7 |
Correct |
4 ms |
11100 KB |
Output is correct |
8 |
Correct |
4 ms |
11100 KB |
Output is correct |
9 |
Correct |
4 ms |
11100 KB |
Output is correct |
10 |
Correct |
4 ms |
11096 KB |
Output is correct |
11 |
Correct |
2 ms |
6744 KB |
Output is correct |
12 |
Correct |
1 ms |
6492 KB |
Output is correct |
13 |
Correct |
2 ms |
10716 KB |
Output is correct |
14 |
Correct |
2 ms |
10704 KB |
Output is correct |
15 |
Correct |
2 ms |
10788 KB |
Output is correct |
16 |
Correct |
2 ms |
10588 KB |
Output is correct |
17 |
Correct |
1 ms |
10588 KB |
Output is correct |
18 |
Correct |
2 ms |
10588 KB |
Output is correct |
19 |
Correct |
2 ms |
10700 KB |
Output is correct |
20 |
Correct |
2 ms |
10588 KB |
Output is correct |
21 |
Correct |
3 ms |
11100 KB |
Output is correct |
22 |
Correct |
3 ms |
11100 KB |
Output is correct |
23 |
Correct |
4 ms |
11100 KB |
Output is correct |
24 |
Correct |
3 ms |
11100 KB |
Output is correct |
25 |
Correct |
4 ms |
11100 KB |
Output is correct |
26 |
Correct |
3 ms |
10972 KB |
Output is correct |
27 |
Correct |
3 ms |
11352 KB |
Output is correct |
28 |
Correct |
4 ms |
11100 KB |
Output is correct |
29 |
Correct |
4 ms |
10964 KB |
Output is correct |
30 |
Correct |
3 ms |
11100 KB |
Output is correct |
31 |
Correct |
3 ms |
11100 KB |
Output is correct |
32 |
Correct |
4 ms |
11100 KB |
Output is correct |
33 |
Correct |
1211 ms |
77140 KB |
Output is correct |
34 |
Correct |
1234 ms |
77120 KB |
Output is correct |
35 |
Correct |
1212 ms |
77988 KB |
Output is correct |
36 |
Correct |
1201 ms |
78524 KB |
Output is correct |
37 |
Correct |
1226 ms |
77220 KB |
Output is correct |
38 |
Correct |
1214 ms |
76976 KB |
Output is correct |
39 |
Correct |
1199 ms |
76708 KB |
Output is correct |
40 |
Correct |
1234 ms |
77256 KB |
Output is correct |
41 |
Correct |
1212 ms |
76960 KB |
Output is correct |
42 |
Correct |
1191 ms |
76984 KB |
Output is correct |
43 |
Correct |
1194 ms |
78140 KB |
Output is correct |
44 |
Correct |
1186 ms |
77220 KB |
Output is correct |
45 |
Correct |
1180 ms |
78020 KB |
Output is correct |
46 |
Correct |
1207 ms |
77244 KB |
Output is correct |
47 |
Correct |
1224 ms |
77736 KB |
Output is correct |
48 |
Correct |
1183 ms |
77984 KB |
Output is correct |
49 |
Correct |
1183 ms |
77744 KB |
Output is correct |
50 |
Correct |
1237 ms |
78012 KB |
Output is correct |
51 |
Correct |
1190 ms |
77984 KB |
Output is correct |
52 |
Correct |
1186 ms |
78256 KB |
Output is correct |
53 |
Correct |
1197 ms |
78492 KB |
Output is correct |
54 |
Correct |
1226 ms |
77484 KB |
Output is correct |
55 |
Correct |
1197 ms |
77480 KB |
Output is correct |
56 |
Correct |
1206 ms |
78516 KB |
Output is correct |
57 |
Correct |
1200 ms |
78004 KB |
Output is correct |
58 |
Correct |
1246 ms |
78004 KB |
Output is correct |
59 |
Correct |
1203 ms |
77480 KB |
Output is correct |
60 |
Correct |
1230 ms |
77992 KB |
Output is correct |
61 |
Correct |
1195 ms |
77156 KB |
Output is correct |
62 |
Correct |
1214 ms |
78008 KB |
Output is correct |
63 |
Correct |
1200 ms |
77368 KB |
Output is correct |
64 |
Correct |
1238 ms |
78244 KB |
Output is correct |
65 |
Incorrect |
1435 ms |
78516 KB |
Output isn't correct |
66 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
11096 KB |
Output is correct |
2 |
Correct |
2 ms |
10972 KB |
Output is correct |
3 |
Correct |
2 ms |
11096 KB |
Output is correct |
4 |
Correct |
3 ms |
11100 KB |
Output is correct |
5 |
Correct |
2 ms |
11100 KB |
Output is correct |
6 |
Correct |
2 ms |
11096 KB |
Output is correct |
7 |
Correct |
3 ms |
11096 KB |
Output is correct |
8 |
Correct |
3 ms |
11100 KB |
Output is correct |
9 |
Correct |
2 ms |
11100 KB |
Output is correct |
10 |
Correct |
2 ms |
11100 KB |
Output is correct |
11 |
Correct |
1 ms |
6488 KB |
Output is correct |
12 |
Correct |
1 ms |
6492 KB |
Output is correct |
13 |
Correct |
2 ms |
10588 KB |
Output is correct |
14 |
Correct |
2 ms |
10712 KB |
Output is correct |
15 |
Correct |
2 ms |
10588 KB |
Output is correct |
16 |
Correct |
3 ms |
11100 KB |
Output is correct |
17 |
Correct |
3 ms |
11096 KB |
Output is correct |
18 |
Correct |
3 ms |
11100 KB |
Output is correct |
19 |
Correct |
4 ms |
11100 KB |
Output is correct |
20 |
Correct |
4 ms |
11100 KB |
Output is correct |
21 |
Correct |
3 ms |
11100 KB |
Output is correct |
22 |
Correct |
4 ms |
11100 KB |
Output is correct |
23 |
Correct |
4 ms |
11100 KB |
Output is correct |
24 |
Correct |
4 ms |
11100 KB |
Output is correct |
25 |
Correct |
4 ms |
11096 KB |
Output is correct |
26 |
Correct |
2 ms |
6744 KB |
Output is correct |
27 |
Correct |
1 ms |
6492 KB |
Output is correct |
28 |
Correct |
2 ms |
10716 KB |
Output is correct |
29 |
Correct |
2 ms |
10704 KB |
Output is correct |
30 |
Correct |
2 ms |
10788 KB |
Output is correct |
31 |
Correct |
2 ms |
10588 KB |
Output is correct |
32 |
Correct |
1 ms |
10588 KB |
Output is correct |
33 |
Correct |
2 ms |
10588 KB |
Output is correct |
34 |
Correct |
2 ms |
10700 KB |
Output is correct |
35 |
Correct |
2 ms |
10588 KB |
Output is correct |
36 |
Correct |
3 ms |
11100 KB |
Output is correct |
37 |
Correct |
3 ms |
11100 KB |
Output is correct |
38 |
Correct |
4 ms |
11100 KB |
Output is correct |
39 |
Correct |
3 ms |
11100 KB |
Output is correct |
40 |
Correct |
4 ms |
11100 KB |
Output is correct |
41 |
Correct |
3 ms |
10972 KB |
Output is correct |
42 |
Correct |
3 ms |
11352 KB |
Output is correct |
43 |
Correct |
4 ms |
11100 KB |
Output is correct |
44 |
Correct |
4 ms |
10964 KB |
Output is correct |
45 |
Correct |
3 ms |
11100 KB |
Output is correct |
46 |
Correct |
3 ms |
11100 KB |
Output is correct |
47 |
Correct |
4 ms |
11100 KB |
Output is correct |
48 |
Correct |
1211 ms |
77140 KB |
Output is correct |
49 |
Correct |
1234 ms |
77120 KB |
Output is correct |
50 |
Correct |
1212 ms |
77988 KB |
Output is correct |
51 |
Correct |
1201 ms |
78524 KB |
Output is correct |
52 |
Correct |
1226 ms |
77220 KB |
Output is correct |
53 |
Correct |
1214 ms |
76976 KB |
Output is correct |
54 |
Correct |
1199 ms |
76708 KB |
Output is correct |
55 |
Correct |
1234 ms |
77256 KB |
Output is correct |
56 |
Correct |
1212 ms |
76960 KB |
Output is correct |
57 |
Correct |
1191 ms |
76984 KB |
Output is correct |
58 |
Correct |
1194 ms |
78140 KB |
Output is correct |
59 |
Correct |
1186 ms |
77220 KB |
Output is correct |
60 |
Correct |
1180 ms |
78020 KB |
Output is correct |
61 |
Correct |
1207 ms |
77244 KB |
Output is correct |
62 |
Correct |
1224 ms |
77736 KB |
Output is correct |
63 |
Correct |
1183 ms |
77984 KB |
Output is correct |
64 |
Correct |
1183 ms |
77744 KB |
Output is correct |
65 |
Correct |
1237 ms |
78012 KB |
Output is correct |
66 |
Correct |
1190 ms |
77984 KB |
Output is correct |
67 |
Correct |
1186 ms |
78256 KB |
Output is correct |
68 |
Correct |
1197 ms |
78492 KB |
Output is correct |
69 |
Correct |
1226 ms |
77484 KB |
Output is correct |
70 |
Correct |
1197 ms |
77480 KB |
Output is correct |
71 |
Correct |
1206 ms |
78516 KB |
Output is correct |
72 |
Correct |
1200 ms |
78004 KB |
Output is correct |
73 |
Correct |
1246 ms |
78004 KB |
Output is correct |
74 |
Correct |
1203 ms |
77480 KB |
Output is correct |
75 |
Correct |
1230 ms |
77992 KB |
Output is correct |
76 |
Correct |
1195 ms |
77156 KB |
Output is correct |
77 |
Correct |
1214 ms |
78008 KB |
Output is correct |
78 |
Correct |
1200 ms |
77368 KB |
Output is correct |
79 |
Correct |
1238 ms |
78244 KB |
Output is correct |
80 |
Incorrect |
1435 ms |
78516 KB |
Output isn't correct |
81 |
Halted |
0 ms |
0 KB |
- |