#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int,int>;
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, int v) {
dat[x+=sz] = v;
pf[x]=sf[x]=mx[x]=max(0, 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;
struct Point {
int x,y,v;
bool operator < (const Point& rhs) const {
return pii(x, y) < pii(rhs.x, rhs.y);
}
};
struct Line {
int x, y, i, j;
bool operator<(const Line &p)const {
return (long long)y*p.x != (long long)p.y*x ? (long long)y*p.x < (long long)p.y*x : i!=p.i?i<p.i:j<p.j;
}
};
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++) {
int dx = p[j].x-p[i].x;
int 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});
}
}
sort(all(lines));
for(int i=0;i<n;i++) {
S.update(i, p[i].v);
pos[i]=i;
}
ll ans = S.get();
int cnt = lines.size();
for (int i = 0,j; i < cnt; i++) {
for (j = i; j < cnt; j++) {
if ((long long)lines[i].x*lines[j].y != (long long)lines[i].y*lines[j].x)break;
int a = lines[j].i, b = lines[j].j;
swap(pos[a], pos[b]);
S.update(pos[a], p[a].v);
S.update(pos[b], p[b].v);
}
ans = max(ans, S.get());
i=j-1;
}
cout<<ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
604 KB |
Output is correct |
2 |
Incorrect |
1 ms |
604 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
604 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
604 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
604 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
604 KB |
Output is correct |
2 |
Incorrect |
1 ms |
604 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |