#include "bits/stdc++.h"
using namespace std;
#define ar array
#define int long long
const int N = 2005;
long double const eps = 1e-14;
struct ST{
ar<int, 4> tree[N * 4];
void merge(ar<int, 4>& x, ar<int, 4>& a, ar<int, 4>& b){
x[0] = max({a[0], b[0], a[2] + b[1]});
x[1] = max({a[1], a[3] + b[1]});
x[2] = max({b[2], b[3] + a[2]});
x[3] = a[3] + b[3];
}
void sett(int i, int v, int lx = 0, int rx = N, int x = 1){
if(lx == rx){
tree[x] = {max(v, 0ll), max(v, 0ll), max(v, 0ll), v}; return;
} int m = (lx + rx) >> 1;
if(i <= m) sett(i, v, lx, m, x<<1);
else sett(i, v, m+1, rx, x<<1|1);
merge(tree[x], tree[x<<1], tree[x<<1|1]);
}
int get(int i, int lx = 0, int rx = N, int x = 1){
if(lx == rx) return tree[x][3];
int m = (lx + rx) >> 1;
if(i <= m) return get(i, lx, m, x<<1);
else return get(i, m+1, rx, x<<1|1);
}
}tree;
/*
5
5 1 5
4 2 2
3 3 -2
2 4 3
1 5 -1
*/
signed main(){
ios::sync_with_stdio(0); cin.tie(0);
int n; cin>>n;
vector<ar<int, 3>> a(n);
for(int i=0;i<n;i++){
cin>>a[i][0]>>a[i][1]>>a[i][2];
} sort(a.begin(), a.end(), [&](auto& a, auto& b){
if(a[0] != b[0]) return a[0] < b[0];
return a[1] > b[1];
});
//~ cout<<"\n";
vector<pair<long double, pair<int, int>>> tt;
for(int i=0;i<n;i++){
for(int j=i+1;j<n;j++){
if(a[i][0] == a[j][0]) continue;
double slop = (a[j][1] - a[i][1]) * 1. / (a[i][0] - a[j][0]);
//~ cout<<i<<" "<<j<<" "<<slop<<"\n";
tt.push_back({slop, {i, j}});
}
}
vector<long double> b(n);
vector<int> p(n); iota(p.begin(), p.end(), 0);
vector<int> pos(n);
for(int i=0;i<n;i++) pos[p[i]] = i, tree.sett(i, a[p[i]][2]);
//~ for(int i=0;i<n;i++){
//~ cout<<p[i]<<" ";
//~ } cout<<"\n";
int res = tree.tree[1][0];
sort(tt.begin(), tt.end(), [&](auto& a, auto& b){
if(a.first != b.first) return a.first < b.first;
if(a.second.second != b.second.second) return a.second.second > b.second.second;
return a.second.first < b.second.first;
});
vector<int> used(n);
for(int l=0;l<(int)tt.size();){
int k = l;
//~ cout<<tt[l].first<<"\n";
while(k < (int)tt.size() && abs(tt[l].first - tt[k].first) < eps){
auto [i, j] = tt[k].second; k++;
if(used[j] || used[i]) continue;
used[j] = used[i] = 1;
//~ cout<<i<<" "<<j<<" "<<pos[i]<<" "<<pos[j]<<"\n";
swap(p[pos[i]], p[pos[j]]);
swap(pos[i], pos[j]);
tree.sett(pos[i], a[i][2]), tree.sett(pos[j], a[j][2]);
//~ k++;
} while(l < k) used[tt[l].second.first] = used[tt[l].second.second] = 0, l++;
//~ for(int i=0;i<n;i++){
//~ cout<<p[i]<<" ";
//~ } cout<<"\n";
res = max(res, tree.tree[1][0]);
}
cout<<res<<"\n";
}
Compilation message
bulldozer.cpp: In function 'int main()':
bulldozer.cpp:91:9: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
91 | auto [i, j] = tt[k].second; k++;
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
716 KB |
Output is correct |
2 |
Correct |
1 ms |
716 KB |
Output is correct |
3 |
Correct |
1 ms |
716 KB |
Output is correct |
4 |
Correct |
1 ms |
716 KB |
Output is correct |
5 |
Correct |
1 ms |
716 KB |
Output is correct |
6 |
Correct |
1 ms |
716 KB |
Output is correct |
7 |
Correct |
1 ms |
716 KB |
Output is correct |
8 |
Correct |
2 ms |
716 KB |
Output is correct |
9 |
Correct |
1 ms |
716 KB |
Output is correct |
10 |
Correct |
1 ms |
716 KB |
Output is correct |
11 |
Correct |
1 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 |
2 ms |
716 KB |
Output is correct |
2 |
Correct |
2 ms |
700 KB |
Output is correct |
3 |
Correct |
2 ms |
716 KB |
Output is correct |
4 |
Correct |
2 ms |
716 KB |
Output is correct |
5 |
Correct |
2 ms |
708 KB |
Output is correct |
6 |
Correct |
2 ms |
716 KB |
Output is correct |
7 |
Correct |
2 ms |
716 KB |
Output is correct |
8 |
Correct |
2 ms |
716 KB |
Output is correct |
9 |
Correct |
2 ms |
716 KB |
Output is correct |
10 |
Correct |
2 ms |
716 KB |
Output is correct |
11 |
Correct |
0 ms |
332 KB |
Output is correct |
12 |
Correct |
0 ms |
332 KB |
Output is correct |
13 |
Correct |
1 ms |
332 KB |
Output is correct |
14 |
Correct |
1 ms |
320 KB |
Output is correct |
15 |
Correct |
1 ms |
332 KB |
Output is correct |
16 |
Correct |
0 ms |
332 KB |
Output is correct |
17 |
Correct |
0 ms |
316 KB |
Output is correct |
18 |
Correct |
0 ms |
332 KB |
Output is correct |
19 |
Correct |
0 ms |
332 KB |
Output is correct |
20 |
Correct |
0 ms |
332 KB |
Output is correct |
21 |
Correct |
2 ms |
716 KB |
Output is correct |
22 |
Correct |
2 ms |
716 KB |
Output is correct |
23 |
Correct |
2 ms |
704 KB |
Output is correct |
24 |
Correct |
2 ms |
716 KB |
Output is correct |
25 |
Correct |
2 ms |
716 KB |
Output is correct |
26 |
Correct |
3 ms |
716 KB |
Output is correct |
27 |
Correct |
2 ms |
716 KB |
Output is correct |
28 |
Correct |
2 ms |
716 KB |
Output is correct |
29 |
Correct |
2 ms |
716 KB |
Output is correct |
30 |
Correct |
2 ms |
716 KB |
Output is correct |
31 |
Correct |
2 ms |
708 KB |
Output is correct |
32 |
Correct |
2 ms |
716 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
716 KB |
Output is correct |
2 |
Correct |
2 ms |
700 KB |
Output is correct |
3 |
Correct |
2 ms |
716 KB |
Output is correct |
4 |
Correct |
2 ms |
716 KB |
Output is correct |
5 |
Correct |
2 ms |
708 KB |
Output is correct |
6 |
Correct |
2 ms |
716 KB |
Output is correct |
7 |
Correct |
2 ms |
716 KB |
Output is correct |
8 |
Correct |
2 ms |
716 KB |
Output is correct |
9 |
Correct |
2 ms |
716 KB |
Output is correct |
10 |
Correct |
2 ms |
716 KB |
Output is correct |
11 |
Correct |
0 ms |
332 KB |
Output is correct |
12 |
Correct |
0 ms |
332 KB |
Output is correct |
13 |
Correct |
1 ms |
332 KB |
Output is correct |
14 |
Correct |
1 ms |
320 KB |
Output is correct |
15 |
Correct |
1 ms |
332 KB |
Output is correct |
16 |
Correct |
0 ms |
332 KB |
Output is correct |
17 |
Correct |
0 ms |
316 KB |
Output is correct |
18 |
Correct |
0 ms |
332 KB |
Output is correct |
19 |
Correct |
0 ms |
332 KB |
Output is correct |
20 |
Correct |
0 ms |
332 KB |
Output is correct |
21 |
Correct |
2 ms |
716 KB |
Output is correct |
22 |
Correct |
2 ms |
716 KB |
Output is correct |
23 |
Correct |
2 ms |
704 KB |
Output is correct |
24 |
Correct |
2 ms |
716 KB |
Output is correct |
25 |
Correct |
2 ms |
716 KB |
Output is correct |
26 |
Correct |
3 ms |
716 KB |
Output is correct |
27 |
Correct |
2 ms |
716 KB |
Output is correct |
28 |
Correct |
2 ms |
716 KB |
Output is correct |
29 |
Correct |
2 ms |
716 KB |
Output is correct |
30 |
Correct |
2 ms |
716 KB |
Output is correct |
31 |
Correct |
2 ms |
708 KB |
Output is correct |
32 |
Correct |
2 ms |
716 KB |
Output is correct |
33 |
Correct |
1016 ms |
66128 KB |
Output is correct |
34 |
Correct |
940 ms |
66180 KB |
Output is correct |
35 |
Correct |
1020 ms |
66256 KB |
Output is correct |
36 |
Correct |
1087 ms |
66128 KB |
Output is correct |
37 |
Correct |
1103 ms |
66144 KB |
Output is correct |
38 |
Correct |
1018 ms |
66148 KB |
Output is correct |
39 |
Correct |
1089 ms |
66180 KB |
Output is correct |
40 |
Correct |
1069 ms |
66204 KB |
Output is correct |
41 |
Correct |
1051 ms |
66148 KB |
Output is correct |
42 |
Correct |
1086 ms |
66128 KB |
Output is correct |
43 |
Correct |
1112 ms |
66188 KB |
Output is correct |
44 |
Correct |
970 ms |
66204 KB |
Output is correct |
45 |
Correct |
1051 ms |
66248 KB |
Output is correct |
46 |
Correct |
973 ms |
66188 KB |
Output is correct |
47 |
Correct |
965 ms |
66172 KB |
Output is correct |
48 |
Correct |
1091 ms |
66148 KB |
Output is correct |
49 |
Correct |
1004 ms |
66212 KB |
Output is correct |
50 |
Correct |
964 ms |
66220 KB |
Output is correct |
51 |
Correct |
1026 ms |
66172 KB |
Output is correct |
52 |
Correct |
1027 ms |
66132 KB |
Output is correct |
53 |
Correct |
981 ms |
66136 KB |
Output is correct |
54 |
Correct |
964 ms |
66160 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
716 KB |
Output is correct |
2 |
Correct |
2 ms |
700 KB |
Output is correct |
3 |
Correct |
2 ms |
716 KB |
Output is correct |
4 |
Correct |
2 ms |
716 KB |
Output is correct |
5 |
Correct |
2 ms |
708 KB |
Output is correct |
6 |
Correct |
2 ms |
716 KB |
Output is correct |
7 |
Correct |
2 ms |
716 KB |
Output is correct |
8 |
Correct |
2 ms |
716 KB |
Output is correct |
9 |
Correct |
2 ms |
716 KB |
Output is correct |
10 |
Correct |
2 ms |
716 KB |
Output is correct |
11 |
Correct |
0 ms |
332 KB |
Output is correct |
12 |
Correct |
0 ms |
332 KB |
Output is correct |
13 |
Correct |
1 ms |
332 KB |
Output is correct |
14 |
Correct |
1 ms |
320 KB |
Output is correct |
15 |
Correct |
1 ms |
332 KB |
Output is correct |
16 |
Correct |
0 ms |
332 KB |
Output is correct |
17 |
Correct |
0 ms |
316 KB |
Output is correct |
18 |
Correct |
0 ms |
332 KB |
Output is correct |
19 |
Correct |
0 ms |
332 KB |
Output is correct |
20 |
Correct |
0 ms |
332 KB |
Output is correct |
21 |
Correct |
2 ms |
716 KB |
Output is correct |
22 |
Correct |
2 ms |
716 KB |
Output is correct |
23 |
Correct |
2 ms |
704 KB |
Output is correct |
24 |
Correct |
2 ms |
716 KB |
Output is correct |
25 |
Correct |
2 ms |
716 KB |
Output is correct |
26 |
Correct |
3 ms |
716 KB |
Output is correct |
27 |
Correct |
2 ms |
716 KB |
Output is correct |
28 |
Correct |
2 ms |
716 KB |
Output is correct |
29 |
Correct |
2 ms |
716 KB |
Output is correct |
30 |
Correct |
2 ms |
716 KB |
Output is correct |
31 |
Correct |
2 ms |
708 KB |
Output is correct |
32 |
Correct |
2 ms |
716 KB |
Output is correct |
33 |
Correct |
1016 ms |
66128 KB |
Output is correct |
34 |
Correct |
940 ms |
66180 KB |
Output is correct |
35 |
Correct |
1020 ms |
66256 KB |
Output is correct |
36 |
Correct |
1087 ms |
66128 KB |
Output is correct |
37 |
Correct |
1103 ms |
66144 KB |
Output is correct |
38 |
Correct |
1018 ms |
66148 KB |
Output is correct |
39 |
Correct |
1089 ms |
66180 KB |
Output is correct |
40 |
Correct |
1069 ms |
66204 KB |
Output is correct |
41 |
Correct |
1051 ms |
66148 KB |
Output is correct |
42 |
Correct |
1086 ms |
66128 KB |
Output is correct |
43 |
Correct |
1112 ms |
66188 KB |
Output is correct |
44 |
Correct |
970 ms |
66204 KB |
Output is correct |
45 |
Correct |
1051 ms |
66248 KB |
Output is correct |
46 |
Correct |
973 ms |
66188 KB |
Output is correct |
47 |
Correct |
965 ms |
66172 KB |
Output is correct |
48 |
Correct |
1091 ms |
66148 KB |
Output is correct |
49 |
Correct |
1004 ms |
66212 KB |
Output is correct |
50 |
Correct |
964 ms |
66220 KB |
Output is correct |
51 |
Correct |
1026 ms |
66172 KB |
Output is correct |
52 |
Correct |
1027 ms |
66132 KB |
Output is correct |
53 |
Correct |
981 ms |
66136 KB |
Output is correct |
54 |
Correct |
964 ms |
66160 KB |
Output is correct |
55 |
Correct |
1016 ms |
66184 KB |
Output is correct |
56 |
Correct |
976 ms |
66192 KB |
Output is correct |
57 |
Correct |
975 ms |
66152 KB |
Output is correct |
58 |
Correct |
1031 ms |
66228 KB |
Output is correct |
59 |
Correct |
959 ms |
66148 KB |
Output is correct |
60 |
Correct |
1024 ms |
66180 KB |
Output is correct |
61 |
Correct |
1107 ms |
66176 KB |
Output is correct |
62 |
Correct |
1067 ms |
66164 KB |
Output is correct |
63 |
Correct |
1072 ms |
66196 KB |
Output is correct |
64 |
Correct |
1086 ms |
66184 KB |
Output is correct |
65 |
Correct |
1051 ms |
66160 KB |
Output is correct |
66 |
Correct |
1071 ms |
66220 KB |
Output is correct |
67 |
Correct |
1076 ms |
66136 KB |
Output is correct |
68 |
Correct |
999 ms |
66200 KB |
Output is correct |
69 |
Correct |
1006 ms |
66188 KB |
Output is correct |
70 |
Correct |
1127 ms |
66216 KB |
Output is correct |
71 |
Correct |
1078 ms |
66176 KB |
Output is correct |
72 |
Correct |
1033 ms |
66216 KB |
Output is correct |
73 |
Correct |
1073 ms |
66100 KB |
Output is correct |
74 |
Correct |
1102 ms |
66152 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
716 KB |
Output is correct |
2 |
Correct |
1 ms |
716 KB |
Output is correct |
3 |
Correct |
1 ms |
716 KB |
Output is correct |
4 |
Correct |
1 ms |
716 KB |
Output is correct |
5 |
Correct |
1 ms |
716 KB |
Output is correct |
6 |
Correct |
1 ms |
716 KB |
Output is correct |
7 |
Correct |
1 ms |
716 KB |
Output is correct |
8 |
Correct |
2 ms |
716 KB |
Output is correct |
9 |
Correct |
1 ms |
716 KB |
Output is correct |
10 |
Correct |
1 ms |
716 KB |
Output is correct |
11 |
Correct |
1 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 |
2 ms |
716 KB |
Output is correct |
17 |
Correct |
2 ms |
700 KB |
Output is correct |
18 |
Correct |
2 ms |
716 KB |
Output is correct |
19 |
Correct |
2 ms |
716 KB |
Output is correct |
20 |
Correct |
2 ms |
708 KB |
Output is correct |
21 |
Correct |
2 ms |
716 KB |
Output is correct |
22 |
Correct |
2 ms |
716 KB |
Output is correct |
23 |
Correct |
2 ms |
716 KB |
Output is correct |
24 |
Correct |
2 ms |
716 KB |
Output is correct |
25 |
Correct |
2 ms |
716 KB |
Output is correct |
26 |
Correct |
0 ms |
332 KB |
Output is correct |
27 |
Correct |
0 ms |
332 KB |
Output is correct |
28 |
Correct |
1 ms |
332 KB |
Output is correct |
29 |
Correct |
1 ms |
320 KB |
Output is correct |
30 |
Correct |
1 ms |
332 KB |
Output is correct |
31 |
Correct |
0 ms |
332 KB |
Output is correct |
32 |
Correct |
0 ms |
316 KB |
Output is correct |
33 |
Correct |
0 ms |
332 KB |
Output is correct |
34 |
Correct |
0 ms |
332 KB |
Output is correct |
35 |
Correct |
0 ms |
332 KB |
Output is correct |
36 |
Correct |
2 ms |
716 KB |
Output is correct |
37 |
Correct |
2 ms |
716 KB |
Output is correct |
38 |
Correct |
2 ms |
704 KB |
Output is correct |
39 |
Correct |
2 ms |
716 KB |
Output is correct |
40 |
Correct |
2 ms |
716 KB |
Output is correct |
41 |
Correct |
3 ms |
716 KB |
Output is correct |
42 |
Correct |
2 ms |
716 KB |
Output is correct |
43 |
Correct |
2 ms |
716 KB |
Output is correct |
44 |
Correct |
2 ms |
716 KB |
Output is correct |
45 |
Correct |
2 ms |
716 KB |
Output is correct |
46 |
Correct |
2 ms |
708 KB |
Output is correct |
47 |
Correct |
2 ms |
716 KB |
Output is correct |
48 |
Correct |
1016 ms |
66128 KB |
Output is correct |
49 |
Correct |
940 ms |
66180 KB |
Output is correct |
50 |
Correct |
1020 ms |
66256 KB |
Output is correct |
51 |
Correct |
1087 ms |
66128 KB |
Output is correct |
52 |
Correct |
1103 ms |
66144 KB |
Output is correct |
53 |
Correct |
1018 ms |
66148 KB |
Output is correct |
54 |
Correct |
1089 ms |
66180 KB |
Output is correct |
55 |
Correct |
1069 ms |
66204 KB |
Output is correct |
56 |
Correct |
1051 ms |
66148 KB |
Output is correct |
57 |
Correct |
1086 ms |
66128 KB |
Output is correct |
58 |
Correct |
1112 ms |
66188 KB |
Output is correct |
59 |
Correct |
970 ms |
66204 KB |
Output is correct |
60 |
Correct |
1051 ms |
66248 KB |
Output is correct |
61 |
Correct |
973 ms |
66188 KB |
Output is correct |
62 |
Correct |
965 ms |
66172 KB |
Output is correct |
63 |
Correct |
1091 ms |
66148 KB |
Output is correct |
64 |
Correct |
1004 ms |
66212 KB |
Output is correct |
65 |
Correct |
964 ms |
66220 KB |
Output is correct |
66 |
Correct |
1026 ms |
66172 KB |
Output is correct |
67 |
Correct |
1027 ms |
66132 KB |
Output is correct |
68 |
Correct |
981 ms |
66136 KB |
Output is correct |
69 |
Correct |
964 ms |
66160 KB |
Output is correct |
70 |
Correct |
1016 ms |
66184 KB |
Output is correct |
71 |
Correct |
976 ms |
66192 KB |
Output is correct |
72 |
Correct |
975 ms |
66152 KB |
Output is correct |
73 |
Correct |
1031 ms |
66228 KB |
Output is correct |
74 |
Correct |
959 ms |
66148 KB |
Output is correct |
75 |
Correct |
1024 ms |
66180 KB |
Output is correct |
76 |
Correct |
1107 ms |
66176 KB |
Output is correct |
77 |
Correct |
1067 ms |
66164 KB |
Output is correct |
78 |
Correct |
1072 ms |
66196 KB |
Output is correct |
79 |
Correct |
1086 ms |
66184 KB |
Output is correct |
80 |
Correct |
1051 ms |
66160 KB |
Output is correct |
81 |
Correct |
1071 ms |
66220 KB |
Output is correct |
82 |
Correct |
1076 ms |
66136 KB |
Output is correct |
83 |
Correct |
999 ms |
66200 KB |
Output is correct |
84 |
Correct |
1006 ms |
66188 KB |
Output is correct |
85 |
Correct |
1127 ms |
66216 KB |
Output is correct |
86 |
Correct |
1078 ms |
66176 KB |
Output is correct |
87 |
Correct |
1033 ms |
66216 KB |
Output is correct |
88 |
Correct |
1073 ms |
66100 KB |
Output is correct |
89 |
Correct |
1102 ms |
66152 KB |
Output is correct |
90 |
Correct |
1075 ms |
66120 KB |
Output is correct |
91 |
Correct |
1048 ms |
66260 KB |
Output is correct |
92 |
Correct |
1082 ms |
66176 KB |
Output is correct |
93 |
Correct |
1020 ms |
66192 KB |
Output is correct |
94 |
Correct |
1120 ms |
66168 KB |
Output is correct |
95 |
Correct |
1041 ms |
66216 KB |
Output is correct |
96 |
Correct |
1097 ms |
66148 KB |
Output is correct |
97 |
Correct |
1100 ms |
66156 KB |
Output is correct |
98 |
Correct |
1102 ms |
66196 KB |
Output is correct |
99 |
Correct |
1082 ms |
66136 KB |
Output is correct |
100 |
Correct |
555 ms |
33340 KB |
Output is correct |
101 |
Correct |
497 ms |
33328 KB |
Output is correct |
102 |
Correct |
452 ms |
33360 KB |
Output is correct |
103 |
Correct |
556 ms |
33304 KB |
Output is correct |
104 |
Correct |
471 ms |
33320 KB |
Output is correct |
105 |
Correct |
718 ms |
66088 KB |
Output is correct |
106 |
Correct |
677 ms |
66088 KB |
Output is correct |
107 |
Correct |
700 ms |
66188 KB |
Output is correct |
108 |
Correct |
742 ms |
66132 KB |
Output is correct |
109 |
Correct |
720 ms |
66152 KB |
Output is correct |
110 |
Correct |
828 ms |
66180 KB |
Output is correct |
111 |
Correct |
865 ms |
66272 KB |
Output is correct |
112 |
Correct |
920 ms |
66200 KB |
Output is correct |
113 |
Correct |
943 ms |
66140 KB |
Output is correct |
114 |
Correct |
1006 ms |
66156 KB |
Output is correct |
115 |
Correct |
883 ms |
66104 KB |
Output is correct |
116 |
Correct |
852 ms |
66140 KB |
Output is correct |
117 |
Correct |
883 ms |
66188 KB |
Output is correct |
118 |
Correct |
933 ms |
66216 KB |
Output is correct |
119 |
Correct |
844 ms |
66144 KB |
Output is correct |
120 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
121 |
Halted |
0 ms |
0 KB |
- |