#include <bits/stdc++.h>
using namespace std;
const int MN = 2e3 + 5;
#define lc ind<<1
#define rc ind<<1|1
struct Node {
long long mn,mx;
} tree[MN<<2];
void update (int ind, int tl, int tr, int i, long long v) {
if (tl == tr) {
tree[ind].mx += v; tree[ind].mn += v;
return;
}
int mid = (tl + tr) / 2;
if (i <= mid) update(lc,tl,mid,i,v);
else update(rc,mid+1,tr,i,v);
tree[ind].mn = min(tree[lc].mn,tree[rc].mn);
tree[ind].mx = max(tree[lc].mx,tree[rc].mx);
}
long long queryMin (int ind, int tl, int tr, int l, int r) {
if (tl > r || tr < l) return LLONG_MAX;
if (l <= tl && tr <= r) return tree[ind].mn;
int mid = (tl + tr) / 2;
return min(queryMin(lc,tl,mid,l,r),queryMin(rc,mid+1,tr,l,r));
}
long long queryMax (int ind, int tl, int tr, int l, int r) {
if (tl > r || tr < l) return LLONG_MIN;
if (l <= tl && tr <= r) return tree[ind].mx;
int mid = (tl + tr) / 2;
return max(queryMax(lc,tl,mid,l,r),queryMax(rc,mid+1,tr,l,r));
}
int main () {
int n,c=0; scanf ("%d",&n);
vector<array<int,4>> pts(n); vector<int> pos(n), ow(n);
vector<long long> vAt(n+1);
for (auto &[x,y,w,id] : pts) scanf ("%d %d %d",&x,&y,&w), id=c++, ow[id] = w;
vector<array<int,4>> events;
for (int i = 0; i < n; i++) {
for (int j = i+1; j < n; j++) {
int dx = pts[i][0] - pts[j][0], dy = pts[i][1] - pts[j][1];
if (dx < 0) dx = -dx, dy = -dy;
if (dx == 0 && dy < 0) dy = -dy;
events.push_back({dx,dy,i,j});
}
}
sort(pts.begin(),pts.end());
sort(events.begin(),events.end(),[&](const auto &a, const auto &b) {return (long long)a[1] * b[0] > (long long)b[1] * a[0];});
long long ret = 0, pre = 0;
for (int i = 0; i < n; i++) {
pos[pts[i][3]] = i+1; ret = max(ret,(long long)pts[i][2]);
pre += pts[i][2]; vAt[i+1] = pre;
update(1,1,n,i+1,pre);
}
for (auto &[x,y,i,j] : events) {
if (pos[i] > pos[j]) swap(i,j);
ret = max(ret,vAt[pos[j]] - min(0LL,queryMin(1,1,n,1,pos[i]-1)) - min(0,ow[i]) - min(0,ow[j]));
ret = max(ret,queryMax(1,1,n,pos[j],n) - (pos[i] == 1 ? 0LL : vAt[pos[i]-1]) - min(0,ow[i]) - min(0,ow[j]));
update(1,1,n,pos[i],ow[j]-ow[i]); vAt[pos[i]] += ow[j] - ow[i];
swap(pos[i],pos[j]);
}
printf ("%lld\n",ret);
return 0;
}
Compilation message
bulldozer.cpp: In function 'int main()':
bulldozer.cpp:33:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
33 | int n,c=0; scanf ("%d",&n);
| ~~~~~~^~~~~~~~~
bulldozer.cpp:36:37: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
36 | for (auto &[x,y,w,id] : pts) scanf ("%d %d %d",&x,&y,&w), id=c++, ow[id] = w;
| ~~~~~~^~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
2 ms |
460 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
460 KB |
Output is correct |
2 |
Correct |
2 ms |
460 KB |
Output is correct |
3 |
Correct |
2 ms |
460 KB |
Output is correct |
4 |
Correct |
2 ms |
464 KB |
Output is correct |
5 |
Correct |
2 ms |
460 KB |
Output is correct |
6 |
Correct |
2 ms |
460 KB |
Output is correct |
7 |
Correct |
2 ms |
460 KB |
Output is correct |
8 |
Correct |
2 ms |
460 KB |
Output is correct |
9 |
Correct |
3 ms |
464 KB |
Output is correct |
10 |
Correct |
2 ms |
460 KB |
Output is correct |
11 |
Correct |
1 ms |
204 KB |
Output is correct |
12 |
Correct |
1 ms |
208 KB |
Output is correct |
13 |
Correct |
1 ms |
204 KB |
Output is correct |
14 |
Correct |
1 ms |
208 KB |
Output is correct |
15 |
Correct |
1 ms |
204 KB |
Output is correct |
16 |
Correct |
1 ms |
204 KB |
Output is correct |
17 |
Correct |
1 ms |
204 KB |
Output is correct |
18 |
Correct |
1 ms |
204 KB |
Output is correct |
19 |
Correct |
1 ms |
204 KB |
Output is correct |
20 |
Correct |
1 ms |
204 KB |
Output is correct |
21 |
Correct |
2 ms |
460 KB |
Output is correct |
22 |
Correct |
2 ms |
460 KB |
Output is correct |
23 |
Correct |
2 ms |
460 KB |
Output is correct |
24 |
Correct |
2 ms |
460 KB |
Output is correct |
25 |
Correct |
3 ms |
460 KB |
Output is correct |
26 |
Correct |
2 ms |
460 KB |
Output is correct |
27 |
Correct |
2 ms |
460 KB |
Output is correct |
28 |
Correct |
2 ms |
460 KB |
Output is correct |
29 |
Correct |
2 ms |
460 KB |
Output is correct |
30 |
Correct |
2 ms |
460 KB |
Output is correct |
31 |
Correct |
2 ms |
460 KB |
Output is correct |
32 |
Correct |
2 ms |
460 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
460 KB |
Output is correct |
2 |
Correct |
2 ms |
460 KB |
Output is correct |
3 |
Correct |
2 ms |
460 KB |
Output is correct |
4 |
Correct |
2 ms |
464 KB |
Output is correct |
5 |
Correct |
2 ms |
460 KB |
Output is correct |
6 |
Correct |
2 ms |
460 KB |
Output is correct |
7 |
Correct |
2 ms |
460 KB |
Output is correct |
8 |
Correct |
2 ms |
460 KB |
Output is correct |
9 |
Correct |
3 ms |
464 KB |
Output is correct |
10 |
Correct |
2 ms |
460 KB |
Output is correct |
11 |
Correct |
1 ms |
204 KB |
Output is correct |
12 |
Correct |
1 ms |
208 KB |
Output is correct |
13 |
Correct |
1 ms |
204 KB |
Output is correct |
14 |
Correct |
1 ms |
208 KB |
Output is correct |
15 |
Correct |
1 ms |
204 KB |
Output is correct |
16 |
Correct |
1 ms |
204 KB |
Output is correct |
17 |
Correct |
1 ms |
204 KB |
Output is correct |
18 |
Correct |
1 ms |
204 KB |
Output is correct |
19 |
Correct |
1 ms |
204 KB |
Output is correct |
20 |
Correct |
1 ms |
204 KB |
Output is correct |
21 |
Correct |
2 ms |
460 KB |
Output is correct |
22 |
Correct |
2 ms |
460 KB |
Output is correct |
23 |
Correct |
2 ms |
460 KB |
Output is correct |
24 |
Correct |
2 ms |
460 KB |
Output is correct |
25 |
Correct |
3 ms |
460 KB |
Output is correct |
26 |
Correct |
2 ms |
460 KB |
Output is correct |
27 |
Correct |
2 ms |
460 KB |
Output is correct |
28 |
Correct |
2 ms |
460 KB |
Output is correct |
29 |
Correct |
2 ms |
460 KB |
Output is correct |
30 |
Correct |
2 ms |
460 KB |
Output is correct |
31 |
Correct |
2 ms |
460 KB |
Output is correct |
32 |
Correct |
2 ms |
460 KB |
Output is correct |
33 |
Correct |
1080 ms |
33328 KB |
Output is correct |
34 |
Correct |
1084 ms |
33364 KB |
Output is correct |
35 |
Correct |
1083 ms |
33304 KB |
Output is correct |
36 |
Correct |
1081 ms |
33316 KB |
Output is correct |
37 |
Correct |
1089 ms |
33308 KB |
Output is correct |
38 |
Correct |
1084 ms |
33312 KB |
Output is correct |
39 |
Correct |
1080 ms |
33308 KB |
Output is correct |
40 |
Correct |
1078 ms |
33316 KB |
Output is correct |
41 |
Correct |
1082 ms |
33304 KB |
Output is correct |
42 |
Correct |
1088 ms |
33288 KB |
Output is correct |
43 |
Correct |
1071 ms |
33308 KB |
Output is correct |
44 |
Correct |
1063 ms |
33316 KB |
Output is correct |
45 |
Correct |
1061 ms |
33308 KB |
Output is correct |
46 |
Correct |
1059 ms |
33320 KB |
Output is correct |
47 |
Correct |
1068 ms |
33308 KB |
Output is correct |
48 |
Correct |
1064 ms |
33328 KB |
Output is correct |
49 |
Correct |
1057 ms |
33304 KB |
Output is correct |
50 |
Correct |
1061 ms |
33316 KB |
Output is correct |
51 |
Correct |
1064 ms |
33316 KB |
Output is correct |
52 |
Correct |
1063 ms |
33320 KB |
Output is correct |
53 |
Correct |
1062 ms |
33320 KB |
Output is correct |
54 |
Correct |
1058 ms |
33300 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
460 KB |
Output is correct |
2 |
Correct |
2 ms |
460 KB |
Output is correct |
3 |
Correct |
2 ms |
460 KB |
Output is correct |
4 |
Correct |
2 ms |
464 KB |
Output is correct |
5 |
Correct |
2 ms |
460 KB |
Output is correct |
6 |
Correct |
2 ms |
460 KB |
Output is correct |
7 |
Correct |
2 ms |
460 KB |
Output is correct |
8 |
Correct |
2 ms |
460 KB |
Output is correct |
9 |
Correct |
3 ms |
464 KB |
Output is correct |
10 |
Correct |
2 ms |
460 KB |
Output is correct |
11 |
Correct |
1 ms |
204 KB |
Output is correct |
12 |
Correct |
1 ms |
208 KB |
Output is correct |
13 |
Correct |
1 ms |
204 KB |
Output is correct |
14 |
Correct |
1 ms |
208 KB |
Output is correct |
15 |
Correct |
1 ms |
204 KB |
Output is correct |
16 |
Correct |
1 ms |
204 KB |
Output is correct |
17 |
Correct |
1 ms |
204 KB |
Output is correct |
18 |
Correct |
1 ms |
204 KB |
Output is correct |
19 |
Correct |
1 ms |
204 KB |
Output is correct |
20 |
Correct |
1 ms |
204 KB |
Output is correct |
21 |
Correct |
2 ms |
460 KB |
Output is correct |
22 |
Correct |
2 ms |
460 KB |
Output is correct |
23 |
Correct |
2 ms |
460 KB |
Output is correct |
24 |
Correct |
2 ms |
460 KB |
Output is correct |
25 |
Correct |
3 ms |
460 KB |
Output is correct |
26 |
Correct |
2 ms |
460 KB |
Output is correct |
27 |
Correct |
2 ms |
460 KB |
Output is correct |
28 |
Correct |
2 ms |
460 KB |
Output is correct |
29 |
Correct |
2 ms |
460 KB |
Output is correct |
30 |
Correct |
2 ms |
460 KB |
Output is correct |
31 |
Correct |
2 ms |
460 KB |
Output is correct |
32 |
Correct |
2 ms |
460 KB |
Output is correct |
33 |
Correct |
1080 ms |
33328 KB |
Output is correct |
34 |
Correct |
1084 ms |
33364 KB |
Output is correct |
35 |
Correct |
1083 ms |
33304 KB |
Output is correct |
36 |
Correct |
1081 ms |
33316 KB |
Output is correct |
37 |
Correct |
1089 ms |
33308 KB |
Output is correct |
38 |
Correct |
1084 ms |
33312 KB |
Output is correct |
39 |
Correct |
1080 ms |
33308 KB |
Output is correct |
40 |
Correct |
1078 ms |
33316 KB |
Output is correct |
41 |
Correct |
1082 ms |
33304 KB |
Output is correct |
42 |
Correct |
1088 ms |
33288 KB |
Output is correct |
43 |
Correct |
1071 ms |
33308 KB |
Output is correct |
44 |
Correct |
1063 ms |
33316 KB |
Output is correct |
45 |
Correct |
1061 ms |
33308 KB |
Output is correct |
46 |
Correct |
1059 ms |
33320 KB |
Output is correct |
47 |
Correct |
1068 ms |
33308 KB |
Output is correct |
48 |
Correct |
1064 ms |
33328 KB |
Output is correct |
49 |
Correct |
1057 ms |
33304 KB |
Output is correct |
50 |
Correct |
1061 ms |
33316 KB |
Output is correct |
51 |
Correct |
1064 ms |
33316 KB |
Output is correct |
52 |
Correct |
1063 ms |
33320 KB |
Output is correct |
53 |
Correct |
1062 ms |
33320 KB |
Output is correct |
54 |
Correct |
1058 ms |
33300 KB |
Output is correct |
55 |
Correct |
1074 ms |
33360 KB |
Output is correct |
56 |
Correct |
1092 ms |
33412 KB |
Output is correct |
57 |
Correct |
1084 ms |
33368 KB |
Output is correct |
58 |
Correct |
1080 ms |
33320 KB |
Output is correct |
59 |
Correct |
1078 ms |
33304 KB |
Output is correct |
60 |
Correct |
1089 ms |
33304 KB |
Output is correct |
61 |
Correct |
1089 ms |
33280 KB |
Output is correct |
62 |
Correct |
1097 ms |
33304 KB |
Output is correct |
63 |
Correct |
1085 ms |
33308 KB |
Output is correct |
64 |
Correct |
1081 ms |
33312 KB |
Output is correct |
65 |
Correct |
1089 ms |
33328 KB |
Output is correct |
66 |
Correct |
1090 ms |
33472 KB |
Output is correct |
67 |
Correct |
1093 ms |
33328 KB |
Output is correct |
68 |
Correct |
1091 ms |
33296 KB |
Output is correct |
69 |
Correct |
1080 ms |
33328 KB |
Output is correct |
70 |
Correct |
1072 ms |
33304 KB |
Output is correct |
71 |
Correct |
1071 ms |
33372 KB |
Output is correct |
72 |
Correct |
1072 ms |
33304 KB |
Output is correct |
73 |
Correct |
1082 ms |
33408 KB |
Output is correct |
74 |
Correct |
1075 ms |
33328 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
2 ms |
460 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |