#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
struct SegTree{
struct node{
ll L, R, sum, mx;
};
vector<node> tree;
int base;
SegTree(int a){
for(base=1 ; base<a ; base<<=1);
tree.resize(base*2);
base--;
}
node add(node &lhs, node &rhs){
node ret;
ret.sum=lhs.sum+rhs.sum;
ret.L=max(lhs.L,lhs.sum+rhs.L);
ret.R=max(rhs.R,rhs.sum+lhs.R);
ret.mx=max({lhs.R+rhs.L, lhs.mx, rhs.mx});
return ret;
}
void updt(int i, ll v){
tree[i+=base]={v,v,v,v};
for(i>>=1 ; i ; i>>=1) tree[i]=add(tree[i*2],tree[i*2+1]);
}
ll qry(){ return tree[1].mx; }
};
struct frac{
ll a, b;
bool operator< (const frac &rhs) const{
return a*rhs.b>rhs.a*b;
}
bool operator== (const frac &rhs) const{
return a*rhs.b==rhs.a*b;
}
};
struct line{
frac slp;
int p1, p2;
bool operator< (const line &rhs) const{
return slp<rhs.slp;
}
};
struct uf{
vector<int> p;
vector<ll> w;
uf(int a) : p(a+5,-1), w(a+5,0) {}
int f(int a){ return p[a]==-1 ? a : p[a]=f(p[a]); }
void u(int x, int y){
x=f(x), y=f(y);
if(x==y) return;
p[x]=y; w[y]+=w[x];
}
};
int N;
pair<P,ll> M[2005];
int id[2005], inv[2005];
//id = sorted state, inv = inverse of id
vector<line> lst;
vector<int> grp[2005];
void fastio(){
ios_base::sync_with_stdio(false); cin.tie(NULL);
}
int main(){
fastio();
cin >> N;
for(int i=1 ; i<=N ; i++){
cin >> M[i].fi.fi >> M[i].fi.se >> M[i].se;
}
if(N==1){
cout << max(0LL,M[1].se) << '\n';
}
vector<frac> F;
sort(M+1,M+1+N);
for(int i=1 ; i<=N ; i++){
for(int j=i+1 ; j<=N ; j++){
lst.pb({{M[i].fi.se-M[j].fi.se, M[i].fi.fi-M[j].fi.fi},i,j});
F.pb(lst.back().slp);
}
}
sort(lst.begin(),lst.end());
sort(F.begin(),F.end());
F.erase(unique(F.begin(),F.end()),F.end());
SegTree seg(N);
uf T(N);
for(int i=1 ; i<=N ; i++) seg.updt(i,M[i].se), id[i]=inv[i]=i, T.w[i]=M[i].se;
int cur=0;
ll ans=0;
for(auto slp : F){
set<int> S;
for(; cur<lst.size() && lst[cur].slp==slp ; cur++){
//union
T.u(lst[cur].p1,lst[cur].p2);
S.insert(lst[cur].p1);
S.insert(lst[cur].p2);
}
vector<int> tmp;
for(int p : S){
if(T.f(p)==p) tmp.pb(p), seg.updt(inv[p],T.w[p]);
else seg.updt(inv[p],0);
grp[T.f(p)].pb(inv[p]);
}
ans=max(ans,seg.qry());
//re-ordering
for(int G : tmp){
sort(grp[G].begin(),grp[G].end());
for(int i=0, j=(int)grp[G].size()-1 ; i<j ; i++, j--){
int x=grp[G][i], y=grp[G][j];
swap(inv[id[x]],inv[id[y]]);
swap(id[x],id[y]);
}
grp[G].clear();
}
//roll back
for(int p : S){
T.w[p]=M[p].se; T.p[p]=-1;
seg.updt(inv[p],T.w[p]);
}
}
cout << ans << '\n';
return 0;
}
Compilation message
bulldozer.cpp: In function 'int main()':
bulldozer.cpp:105:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<line>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
105 | for(; cur<lst.size() && lst[cur].slp==slp ; cur++){
| ~~~^~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
1 ms |
724 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
724 KB |
Output is correct |
2 |
Correct |
3 ms |
636 KB |
Output is correct |
3 |
Correct |
3 ms |
724 KB |
Output is correct |
4 |
Correct |
3 ms |
724 KB |
Output is correct |
5 |
Correct |
3 ms |
636 KB |
Output is correct |
6 |
Correct |
3 ms |
724 KB |
Output is correct |
7 |
Correct |
3 ms |
724 KB |
Output is correct |
8 |
Correct |
3 ms |
724 KB |
Output is correct |
9 |
Correct |
3 ms |
724 KB |
Output is correct |
10 |
Correct |
2 ms |
724 KB |
Output is correct |
11 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
12 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
724 KB |
Output is correct |
2 |
Correct |
3 ms |
636 KB |
Output is correct |
3 |
Correct |
3 ms |
724 KB |
Output is correct |
4 |
Correct |
3 ms |
724 KB |
Output is correct |
5 |
Correct |
3 ms |
636 KB |
Output is correct |
6 |
Correct |
3 ms |
724 KB |
Output is correct |
7 |
Correct |
3 ms |
724 KB |
Output is correct |
8 |
Correct |
3 ms |
724 KB |
Output is correct |
9 |
Correct |
3 ms |
724 KB |
Output is correct |
10 |
Correct |
2 ms |
724 KB |
Output is correct |
11 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
12 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
724 KB |
Output is correct |
2 |
Correct |
3 ms |
636 KB |
Output is correct |
3 |
Correct |
3 ms |
724 KB |
Output is correct |
4 |
Correct |
3 ms |
724 KB |
Output is correct |
5 |
Correct |
3 ms |
636 KB |
Output is correct |
6 |
Correct |
3 ms |
724 KB |
Output is correct |
7 |
Correct |
3 ms |
724 KB |
Output is correct |
8 |
Correct |
3 ms |
724 KB |
Output is correct |
9 |
Correct |
3 ms |
724 KB |
Output is correct |
10 |
Correct |
2 ms |
724 KB |
Output is correct |
11 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
12 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
1 ms |
724 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |