#include<bits/stdc++.h>
#define st first
#define nd second
#define mp make_pair
#define pb push_back
#define pp pop_back
#define eb emplace_back
#define all(x) x.begin(), x.end()
using namespace std;
using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using vi = vector<int>;
void debug(){cerr<<"\n";}
template<typename H, typename... T>
void debug(H h, T... t){
cerr<<h;
if(sizeof...(t))cerr<<", ";
debug(t...);
}
#define deb(x...) cerr<<#x<<" = ";debug(x);
mt19937 rng(chrono::high_resolution_clock().now().time_since_epoch().count());
const int N=(1<<11), INF=1e9+5;
int wei[N], gdzie[N], gdzie2[N];
ll val[N+N], pref[N+N], suf[N+N], res[N+N];
vector<pii> V2;
ll ans=0;
int n;
void dodaj(int v, int c){
val[v+N]+=c;
pref[v+N]=max(val[v+N], 0ll);
suf[v+N]=max(val[v+N], 0ll);
res[v+N]=max(val[v+N], 0ll);
v+=N;
v/=2;
while(v){
int l=v+v, r=l+1;
res[v]=max(res[l], res[r]);
pref[v]=max(pref[l], val[l]+pref[r]);
suf[v]=max(suf[r], val[r]+suf[l]);
val[v]=val[l]+val[r];
res[v]=max(res[v], pref[r]+suf[l]);
v/=2;
}
}
ll get_ans(){
/*ll dp=0, res=0;
for(int i=n-1; i>=0; i--){
dp=max(dp+val[i+N], 0ll);
res=max(res, dp);
}
deb(res);*/
//deb(res[1])
return res[1];
}
/*void zmien(vector<int> V){
/*sort(all(V), [](int a, int b){return gdzie[a]<gdzie[b];});
//assert(V.size()==2);
int c=gdzie[V[0]];
ans=max(ans, get_ans());
for(int i=V.size()-1; i>0;i--){
dodaj(c, wei[V[i]]);
dodaj(gdzie[V[i]], -wei[V[i]]);
}
ans=max(ans, get_ans());
for(int i=V.size()-1; i>=0; i--){
if(i<=V.size()-1-i)break;
swap(gdzie[V[i]], gdzie[V[V.size()-i-1]]);
}
reverse(all(V));
for(int i=V.size()-1; i>0;i--){
dodaj(c, -wei[V[i]]);
dodaj(gdzie[V[i]], wei[V[i]]);
}
ans=max(ans, get_ans());
//for(int i=0; i<n; i++)cout<<gdzie[i]<<" ";cout<<"\n";
//assert(abs(gdzie[V[0]]-gdzie[V[1]])==1);
//deb(V[0], V[1], gdzie[V[0]], gdzie[V[1]]);
ans=max(ans, get_ans());
dodaj(gdzie[V[0]], wei[V[1]]);
dodaj(gdzie[V[1]], -wei[V[1]]);
ans=max(ans, get_ans());
//deb(val[N], val[N+1], val[N+2], val[N+3]);
dodaj(gdzie[V[0]], -wei[V[0]]);
dodaj(gdzie[V[1]], wei[V[0]]);
swap(gdzie[V[0]], gdzie[V[1]]);
ans=max(ans, get_ans());
}*/
vector<int> co[N];
int M[N];
void upd(vector<pii> V){
//deb(V.size());
vi uzy;
for(pii i:V){
//deb(i.st, i.nd);
uzy.pb(i.st);
uzy.pb(i.nd);
M[i.st]=gdzie[i.st];
M[i.nd]=gdzie[i.nd];
}
//deb();
sort(uzy.begin(), uzy.end());
uzy.resize(unique(all(uzy))-uzy.begin());
for(pii i:V){
M[i.nd]=min(M[i.nd], gdzie[i.st]);
M[i.st]=min(M[i.st], gdzie[i.nd]);
}
vi waz;
for(int i:uzy){
//deb(i);
co[M[i]].pb(i);
if(M[i]==gdzie[i])waz.pb(M[i]);
else {
//deb(i, gdzie[i], M[i]);
dodaj(gdzie[i], -wei[i]);
dodaj(M[i], wei[i]);
}
}
ans=max(ans, get_ans());
for(int i:waz){
for(int j:co[i]){
gdzie[j]=co[i].size()-1+2*i-gdzie[j];
}
}
for(int i:uzy){
if(M[i]!=gdzie[i]){
dodaj(gdzie[i], wei[i]);
dodaj(M[i], -wei[i]);
}
}
ans=max(ans, get_ans());
for(auto i:waz){
co[i].clear();
}
}
int main(){
cin>>n;
V2.resize(n);
for(int i=0; i<n; i++)cin>>V2[i].st>>V2[i].nd>>wei[i], gdzie2[i]=i;
sort(gdzie2, gdzie2+n, [](int a, int b){if(V2[a].st==V2[b].st)return V2[a].nd>V2[b].nd;return V2[a].st<V2[b].st;});
for(int i=0; i<n; i++)gdzie[gdzie2[i]]=i;
for(int i=0; i<n; i++)dodaj(gdzie[i], wei[i]);
vector<pair<ld, pii> > V;
for(int i=0; i<n; i++){
for(int j=0; j<i; j++){
int x=V2[i].st-V2[j].st, y=V2[i].nd-V2[j].nd;
if(x>0)y=-y, x=-x;
if(x==0 && y<0)y=-y;
ld kat=-atan2(x, y);
//deb(kat, x, y, i, j);
V.eb(kat, mp(i, j));
}
}
sort(all(V));
vector<pii> todo;
ans=max(ans, get_ans());
for(int i=0; i<V.size(); i++){
todo.pb(V[i].nd);
if(i==n-1 || V[i].st+1e-10>V[i+1].st){
upd(todo);
todo.clear();
}
//zmien({V[i].nd.st, V[i].nd.nd});
}
cout<<ans;
}
Compilation message
bulldozer.cpp:57:2: warning: "/*" within comment [-Wcomment]
57 | /*sort(all(V), [](int a, int b){return gdzie[a]<gdzie[b];});
|
bulldozer.cpp: In function 'int main()':
bulldozer.cpp:157:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long double, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
157 | for(int i=0; i<V.size(); i++){
| ~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
1260 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
724 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
724 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
724 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
1260 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
