#include <bits/stdc++.h>
#define int long long
using namespace std;
const int NS = 2004;
int n;
vector<int> a[2004];
struct Line{
int id1, id2, dx, dy;
Line(){}
Line(int id1, int id2, int dx, int dy):id1(id1), id2(id2), dx(dx), dy(dy){}
bool operator<(const Line&r)const{
return vector<int>{dx * r.dy, id1, id2} < vector<int>{r.dx * dy, r.id1, r.id2};
}
};
Line srt[2004 * 2004];
int num[2004], pos[2004], chk[2004];
int srtN;
int tr[NS * 4], lmax[NS * 4], rmax[NS * 4], sum[NS * 4];
void push(int x, int s, int e, int p, int val){
if(p < s || p > e) return;
if(s == e){
tr[x] += val; sum[x] += val;
lmax[x] = rmax[x] = max(0ll, tr[x]);
return;
}
int m = s + e >> 1;
push(x * 2, s, m, p, val), push(x * 2 + 1, m + 1, e, p, val);
tr[x] = max({tr[x * 2], tr[x * 2 + 1], rmax[x * 2] + lmax[x * 2 + 1]});
rmax[x] = max({rmax[x * 2 + 1], sum[x * 2 + 1] + rmax[x * 2]});
lmax[x] = max({lmax[x * 2], sum[x * 2] + lmax[x * 2 + 1]});
sum[x] = sum[x * 2] + sum[x * 2 + 1];
}
signed main(){
cin >> n;
for(int i = 0; i < n; ++i){
a[i].resize(3);
cin >> a[i][0] >> a[i][1] >> a[i][2];
}
if(n == 1){
cout << max(0ll, a[0][2]) << '\n';
return 0;
}
sort(a, a + n);
for(int i = 0; i < n; ++i){
for(int j = i + 1; j < n; ++j){
srt[srtN++] = Line(i, j, a[j][0] - a[i][0], a[j][1] - a[i][1]);
}
}
sort(srt, srt + srtN);
memset(num, -1, sizeof(num));
for(int i = 0; i < n; ++i){
pos[i] = i;
push(1, 0, n - 1, i, a[i][2]);
}
int ans = 0;
for(int i = 0; i < srtN;){
int j = i;
while(j < srtN && srt[i].dx * srt[j].dy == srt[i].dy * srt[j].dx){
++j;
}
for(int k = i; k < j; ++k){
if(num[srt[k].id1] == -1) num[srt[k].id1] = srt[k].id1;
if(num[srt[k].id2] == -1) num[srt[k].id2] = srt[k].id2;
num[srt[k].id2] = min(num[srt[k].id2], srt[k].id1);
}
for(int k = i; k < j; ++k){
if(!chk[srt[k].id2]){
chk[srt[k].id2] = 1;
push(1, 0, n - 1, pos[srt[k].id2], -a[srt[k].id2][2]);
push(1, 0, n - 1, pos[num[srt[k].id2]], a[srt[k].id2][2]);
}
}
if(tr[1] == 19){
cout << srt[i].dx << ' ' << srt[i].dy << endl;
}
ans = max(ans, tr[1]);
for(int k = i; k < j; ++k){
if(chk[srt[k].id2]){
chk[srt[k].id2] = 0;
push(1, 0, n - 1, pos[srt[k].id2], a[srt[k].id2][2]);
push(1, 0, n - 1, pos[num[srt[k].id2]], -a[srt[k].id2][2]);
}
}
for(int k = i; k < j; ++k){
num[srt[k].id1] = num[srt[k].id2] = -1;
}
for(int k = i; k < j; ++k){
swap(pos[srt[k].id1], pos[srt[k].id2]);
push(1, 0, n - 1, pos[srt[k].id1], a[srt[k].id1][2] - a[srt[k].id2][2]);
push(1, 0, n - 1, pos[srt[k].id2], a[srt[k].id2][2] - a[srt[k].id1][2]);
}
i = j;
}
cout << ans << '\n';
return 0;
}
Compilation message
bulldozer.cpp: In function 'void push(long long int, long long int, long long int, long long int, long long int)':
bulldozer.cpp:29:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
29 | int m = s + e >> 1;
| ~~^~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
5 ms |
512 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
7 ms |
520 KB |
Output is correct |
2 |
Correct |
7 ms |
468 KB |
Output is correct |
3 |
Correct |
5 ms |
524 KB |
Output is correct |
4 |
Correct |
6 ms |
468 KB |
Output is correct |
5 |
Correct |
6 ms |
520 KB |
Output is correct |
6 |
Correct |
5 ms |
468 KB |
Output is correct |
7 |
Correct |
6 ms |
468 KB |
Output is correct |
8 |
Correct |
6 ms |
468 KB |
Output is correct |
9 |
Correct |
5 ms |
468 KB |
Output is correct |
10 |
Correct |
6 ms |
468 KB |
Output is correct |
11 |
Correct |
0 ms |
340 KB |
Output is correct |
12 |
Correct |
0 ms |
340 KB |
Output is correct |
13 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
14 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
7 ms |
520 KB |
Output is correct |
2 |
Correct |
7 ms |
468 KB |
Output is correct |
3 |
Correct |
5 ms |
524 KB |
Output is correct |
4 |
Correct |
6 ms |
468 KB |
Output is correct |
5 |
Correct |
6 ms |
520 KB |
Output is correct |
6 |
Correct |
5 ms |
468 KB |
Output is correct |
7 |
Correct |
6 ms |
468 KB |
Output is correct |
8 |
Correct |
6 ms |
468 KB |
Output is correct |
9 |
Correct |
5 ms |
468 KB |
Output is correct |
10 |
Correct |
6 ms |
468 KB |
Output is correct |
11 |
Correct |
0 ms |
340 KB |
Output is correct |
12 |
Correct |
0 ms |
340 KB |
Output is correct |
13 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
14 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
7 ms |
520 KB |
Output is correct |
2 |
Correct |
7 ms |
468 KB |
Output is correct |
3 |
Correct |
5 ms |
524 KB |
Output is correct |
4 |
Correct |
6 ms |
468 KB |
Output is correct |
5 |
Correct |
6 ms |
520 KB |
Output is correct |
6 |
Correct |
5 ms |
468 KB |
Output is correct |
7 |
Correct |
6 ms |
468 KB |
Output is correct |
8 |
Correct |
6 ms |
468 KB |
Output is correct |
9 |
Correct |
5 ms |
468 KB |
Output is correct |
10 |
Correct |
6 ms |
468 KB |
Output is correct |
11 |
Correct |
0 ms |
340 KB |
Output is correct |
12 |
Correct |
0 ms |
340 KB |
Output is correct |
13 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
14 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
5 ms |
512 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |