#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;
typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;
typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;
template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;
#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)
#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
const int MOD = 1000000007;
const ll INF = 1e18;
const int MX = 2000;
int ad(int a, int b) { return a+b; }
int sub(int a, int b) { return a-b; }
pi operator+(const pi& l, const pi& r) { return {ad(l.f,r.f),ad(l.s,r.s)}; }
pi operator-(const pi& l, const pi& r) { return {sub(l.f,r.f),sub(l.s,r.s)}; }
pi operator+=(pi& l, const pi& r) { return l = l+r; }
pi operator-=(pi& l, const pi& r) { return l = l-r; }
int N;
pair<pi,int> A[MX];
bool done[MX][MX];
vector<pair<pi,vi>> al;
ll ans = 0;
struct node {
ll sum,mn,mx,ans;
node(int w) {
sum = w;
mn = min(0,w);
mx = ans = max(0,w);
}
node(): node(0) {}
};
node comb(const node& l, const node& r) {
node res(0);
res.ans = max(max(l.ans,r.ans),l.sum+r.mx-l.mn);
res.mn = min(l.sum+r.mn,l.mn);
res.mx = max(l.sum+r.mx,l.mx);
res.sum = l.sum+r.sum;
return res;
};
struct Seg {
int ind[2000], rind[2000];
node seg[4096];
void init() {
F0R(i,N) {
rind[i] = ind[i] = i;
seg[i^(1<<11)] = node(A[i].s);
}
FORd(i,1,11) seg[i] = comb(seg[2*i],seg[2*i+1]);
}
void upd(int ind) {
ind ^= (1<<11);
for (ind /= 2; ind; ind /= 2) seg[ind] = comb(seg[2*ind],seg[2*ind+1]);
}
void flip(vi v) {
int mn = MOD, mx = -MOD;
for (int i: v) mn = min(mn,ind[i]), mx = max(mx,ind[i]);
assert(mx-mn+1 == sz(v));
for (int i = mn; i < mx+mn-i; ++i) {
swap(seg[i^(1<<11)],seg[(mx+mn-i)^(1<<11)]);
swap(rind[i],rind[mx+mn-i]);
swap(ind[rind[i]],ind[rind[mx+mn-i]]);
upd(i);
upd(mx+mn-i);
}
}
};
Seg S;
void ins(vi v) {
F0R(i,sz(v)) FOR(j,i+1,sz(v)) done[v[i]][v[j]] = done[v[j]][v[i]] = 1;
al.pb({A[v[1]].f-A[v[0]].f,v});
}
ll cross(pi b, pi c) {
return (ll)b.f*c.s-(ll)b.s*c.f;
}
ll cross(pi a, pi b, pi c) { return cross(b-a,c-a); }
bool cmp(pi a, pi b) { return cross(a,b) > 0; }
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> N;
F0R(i,N) cin >> A[i].f.f >> A[i].f.s >> A[i].s;
sort(A,A+N,[](pair<pi,int> x, pair<pi,int> y) {
if (x.f.s != y.f.s) return x.f.s < y.f.s;
return x.f.f < y.f.f;
});
S.init();
/*F0R(i,N) cout << A[i].f.f << " " << A[i].f.s << "\n";
cout << "\n";*/
F0R(i,N) {
vi v; FOR(j,i+1,N) v.pb(j);
sort(all(v),[&i](int a, int b) { return cmp(A[a].f-A[i].f,A[b].f-A[i].f); });
for (int ind = 0; ind < sz(v); ) {
if (done[i][v[ind]]) {
ind ++;
continue;
}
int IND = ind;
vi tmp = {i};
while (ind < sz(v) && cross(A[i].f,A[v[IND]].f,A[v[ind]].f) == 0) tmp.pb(v[ind++]);
// cout << "OOPS " << IND << " " << ind << "\n";
// cout << A[i].f << " " << A[IND].f << " " << A[ind].f << "\n";
ins(tmp);
}
/*cout << A[i].f.f << " " << A[i].f.s << "\n";
for (auto x: v) cout << A[x].f.f << " " << A[x].f.s << " | ";
cout << "\n";*/
}
sort(all(al), [](pair<pi,vi> a, pair<pi,vi> b) { return cmp(a.f,b.f); });
/*for (auto a: al) {
cout << a.f.f << " " << a.f.s << " | ";
for (int i: a.s) cout << i << " ";
cout << "\n";
}*/
for (int i = 0; i < sz(al); ) {
int I = i;
while (i < sz(al) && cross(al[I].f,al[i].f) == 0) S.flip(al[i++].s);
ans = max(ans,S.seg[1].ans);
}
cout << ans;
}
/* Look for:
* the exact constraints (multiple sets are too slow for n=10^6 :( )
* special cases (n=1?)
* overflow (ll vs int?)
* array bounds
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
768 KB |
Output is correct |
| 2 |
Correct |
2 ms |
768 KB |
Output is correct |
| 3 |
Correct |
2 ms |
640 KB |
Output is correct |
| 4 |
Correct |
3 ms |
640 KB |
Output is correct |
| 5 |
Correct |
2 ms |
640 KB |
Output is correct |
| 6 |
Correct |
2 ms |
640 KB |
Output is correct |
| 7 |
Correct |
2 ms |
640 KB |
Output is correct |
| 8 |
Correct |
2 ms |
768 KB |
Output is correct |
| 9 |
Correct |
2 ms |
640 KB |
Output is correct |
| 10 |
Correct |
2 ms |
640 KB |
Output is correct |
| 11 |
Correct |
2 ms |
512 KB |
Output is correct |
| 12 |
Incorrect |
2 ms |
512 KB |
Output isn't correct |
| 13 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
1152 KB |
Output is correct |
| 2 |
Correct |
10 ms |
1152 KB |
Output is correct |
| 3 |
Incorrect |
9 ms |
1152 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
1152 KB |
Output is correct |
| 2 |
Correct |
10 ms |
1152 KB |
Output is correct |
| 3 |
Incorrect |
9 ms |
1152 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
1152 KB |
Output is correct |
| 2 |
Correct |
10 ms |
1152 KB |
Output is correct |
| 3 |
Incorrect |
9 ms |
1152 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
768 KB |
Output is correct |
| 2 |
Correct |
2 ms |
768 KB |
Output is correct |
| 3 |
Correct |
2 ms |
640 KB |
Output is correct |
| 4 |
Correct |
3 ms |
640 KB |
Output is correct |
| 5 |
Correct |
2 ms |
640 KB |
Output is correct |
| 6 |
Correct |
2 ms |
640 KB |
Output is correct |
| 7 |
Correct |
2 ms |
640 KB |
Output is correct |
| 8 |
Correct |
2 ms |
768 KB |
Output is correct |
| 9 |
Correct |
2 ms |
640 KB |
Output is correct |
| 10 |
Correct |
2 ms |
640 KB |
Output is correct |
| 11 |
Correct |
2 ms |
512 KB |
Output is correct |
| 12 |
Incorrect |
2 ms |
512 KB |
Output isn't correct |
| 13 |
Halted |
0 ms |
0 KB |
- |
