This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
#define x first
#define y second
#define all(v) (v).begin(), (v).end()
const int sz = 2020;
struct Seg {
ll dat[sz*2], sf[sz*2], pf[sz*2], mx[sz*2];
void update(int x, ll v) {
dat[x+=sz] = v;
pf[x]=sf[x]=mx[x]=max(0LL, v);
for(x/=2;x;x/=2) {
pf[x] = max(pf[2*x], dat[2*x]+pf[2*x+1]);
sf[x] = max(sf[2*x+1], dat[2*x+1]+sf[2*x]);
mx[x] = max({mx[2*x],mx[2*x+1], sf[2*x]+pf[2*x+1]});
dat[x] = dat[2*x]+dat[2*x+1];
}
}
ll get() {
return mx[1];
}
} S;
const int SZ = 2048;
struct Tree {
long long L[SZ + SZ], R[SZ + SZ], S[SZ + SZ], M[SZ + SZ];
void Put(int a, int b) {
a += SZ;
S[a] = b;
L[a] = R[a] = M[a] = max(0, b);
while (a != 1) {
a >>= 1;
S[a] = S[a + a] + S[a + a + 1];
L[a] = max(L[a + a], S[a + a] + L[a + a + 1]);
R[a] = max(R[a + a + 1], S[a + a + 1] + R[a + a]);
M[a] = max(max(M[a + a], M[a + a + 1]), R[a + a] + L[a + a + 1]);
}
}
}T;
struct Point {
ll x,y,v;
bool operator < (const Point& rhs) const {
return pll(x, y) < pll(rhs.x, rhs.y);
}
};
struct Line {
ll dx,dy,i,j;
bool operator < (const Line& rhs) const {
ll l = dy*rhs.dx, r = dx*rhs.dy;
return tie(l, i, j) < tie(r, rhs.i, rhs.j);
}
bool operator == (const Line& rhs) const {
ll l = dy*rhs.dx, r = dx*rhs.dy;
return l==r;
}
};
int main(void){
cin.tie(0)->sync_with_stdio(0);
int n; cin>>n;
vector<Point> p(n);
for(auto& [x,y,v]:p) cin>>x>>y>>v;
sort(all(p));
vector<int> pos(n);
vector<Line> lines;
for(int i=0;i<n;i++) {
for(int j=i+1;j<n;j++) {
ll dx = p[j].x-p[i].x;
ll dy = p[j].y-p[i].y;
if (dx < 0 || (dx == 0 && dy < 0))dx = -dx, dy = -dy;
lines.push_back({dx,dy,i,j});
}
}
for(int i=0;i<n;i++) {
T.Put(i, p[i].v);
pos[i]=i;
}
sort(all(lines));
ll ans = T.M[1];
for(int i=0;i<lines.size();i++) {
int a = lines[i].i, b = lines[i].j;
swap(pos[a], pos[b]);
T.Put(pos[a], p[a].v);
T.Put(pos[b], p[b].v);
if(i+1<lines.size() && lines[i] == lines[i+1]) continue;
ans = max(ans, T.M[1]);
}
cout<<ans;
}
Compilation message (stderr)
bulldozer.cpp: In function 'int main()':
bulldozer.cpp:98:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Line>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
98 | for(int i=0;i<lines.size();i++) {
| ~^~~~~~~~~~~~~
bulldozer.cpp:105:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Line>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
105 | if(i+1<lines.size() && lines[i] == lines[i+1]) continue;
| ~~~^~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |