#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#define R(i,n,...) for(int i=__VA_ARGS__+0; i<n; i++)
using namespace std;
struct node {
long mx, lm, rm, sum;
node operator+(const node R) const {
return {
max({mx, R.mx, rm+R.lm}),
max(lm, sum+R.lm),
max(R.rm, rm+R.sum),
sum+R.sum
};
}
};
struct pii {
int x, y;
bool operator<(pii b) const { return x<b.x || x==b.x && y<b.y; }
pii operator-(pii b) const { return {x-b.x, y-b.y}; }
long operator^(pii b) const { return 1LL*x*b.y-1LL*y*b.x; }
};
union evt {
struct { unsigned short i, j; };
unsigned int k;
};
int main() {
ios::sync_with_stdio(0);cin.tie(0);
int N, K=0;
cin>>N;
pii A[N];
int W[N], P[N];
iota(P, P+N, 0);
R(i, N) cin>>A[i].x>>A[i].y>>W[i];
sort(A, A+N);
evt E[N*(N-1)/2];
R(i, N) R(j, i) E[K].i=i, E[K++].j=j;
sort(E, E+K, [&](evt l, evt r) {
auto x=A[l.i]-A[l.j]^A[r.i]-A[r.j];
return x<0 || !x && l.k<r.k;
});
node T[4096]{};
auto upd=[&](int i, int x) {
for(T[i|=2048]={x, x, x, x}; i>>=1;)
T[i]=T[i*2]+T[i*2+1];
};
for(int i=0; i<N; i++) {
int x=W[i];
T[i+2048]={x, x, x, x};
}
for(int i=2048; i--;)
T[i]=T[i*2]+T[i*2+1];
long mx=T[1].mx;
for(int k=0; k<K; k++) {
int i=E[k].i, j=E[k].j;
swap(P[i], P[j]);
upd(P[i], W[i]);
upd(P[j], W[j]);
if(k+1<K && !(A[i]-A[j]^A[E[k+1].i]-A[E[k+1].j])) continue;
mx=max(mx, T[1].mx);
}
cout<<mx;
}
Compilation message
bulldozer.cpp: In member function 'bool pii::operator<(pii) const':
bulldozer.cpp:19:55: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
19 | bool operator<(pii b) const { return x<b.x || x==b.x && y<b.y; }
| ~~~~~~~^~~~~~~~
bulldozer.cpp: In lambda function:
bulldozer.cpp:42:16: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
42 | auto x=A[l.i]-A[l.j]^A[r.i]-A[r.j];
| ~~~~~~^~~~~~~
bulldozer.cpp:43:20: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
43 | return x<0 || !x && l.k<r.k;
| ~~~^~~~~~~~~~
bulldozer.cpp: In function 'int main()':
bulldozer.cpp:64:21: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
64 | if(k+1<K && !(A[i]-A[j]^A[E[k+1].i]-A[E[k+1].j])) continue;
| ~~~~^~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
512 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
512 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
512 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
512 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
512 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
