#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define pb push_back
#define ff first
#define ss second
struct ST{
struct node{
ll pr, sf, mx, s;
};
vector<node> t;
int n;
ST(int ns){
n = ns;
t.resize(4 * n);
}
void upd(int v, int tl, int tr, int& p, int& x){
if (tl == tr){
t[v].s = x;
t[v].pr = t[v].sf = t[v].mx = max(0, x);
return;
}
int tm = (tl + tr) / 2, vv = 2 * v;
if (p <= tm){
upd(vv, tl, tm, p, x);
}
else {
upd(vv + 1, tm + 1, tr, p, x);
}
t[v].s = t[vv].s + t[vv + 1].s;
t[v].mx = max({t[vv].mx, t[vv + 1].mx, t[vv].sf + t[vv + 1].pr});
t[v].pr = max(t[vv].pr, t[vv].s + t[vv + 1].pr);
t[v].sf = max(t[vv + 1].sf, t[vv + 1].s + t[vv].sf);
}
void upd(int p, int x){
upd(1, 1, n, p, x);
}
ll get(){
return t[1].mx;
}
};
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n; cin>>n;
vector<int> x(n + 1), y(n + 1), a(n + 1), f = {0};
for (int i = 1; i <= n; i++){
cin>>x[i]>>y[i]>>a[i];
f.pb(i);
}
auto cmp = [&](int i, int j){
if (x[i] == x[j]){
return y[i] < y[j];
}
return x[i] < x[j];
};
sort(f.begin() + 1, f.end(), cmp);
vector<int> p(n + 1);
for (int i = 1; i <= n; i++){
p[f[i]] = i;
}
ST T(n);
for (int i = 1; i <= n; i++){
T.upd(p[i], a[i]);
}
ll out = T.get();
vector<pair<pii, pii>> all;
for (int i = 1; i <= n; i++){
for (int j = i + 1; j <= n; j++){
if (x[f[i]] != x[f[j]]){
all.pb({{y[f[j]] - y[f[i]], x[f[j]] - x[f[i]]}, {f[i], f[j]}});
}
}
}
auto cmp1 = [&](pair<pii, pii> a, pair<pii, pii> b){
auto [u1, v1] = a.ff;
auto [u2, v2] = b.ff;
return 1LL * u1 * v2 < 1LL * u2 * v1;
};
sort(all.begin(), all.end(), cmp1);
vector<bool> used(n + 1);
vector<int> ff, pp;
int i = 0;
while (i < all.size()){
int j = i;
while (j < all.size() && (1LL * all[i].ff.ff * all[j].ff.ss) == (1LL * all[i].ff.ss * all[j].ff.ff)){
j++;
}
ll r, q;
if (j == all.size()){
r = 2e9 + 1;
q = 1;
}
else {
r = all[i].ff.ff + all[j].ff.ff;
q = all[i].ff.ss + all[j].ff.ss;
assert(q * all[i].ff.ff < r * all[i].ff.ss);
assert(r * all[j].ff.ss < q * all[j].ff.ff);
// all[i].ff.ff / all[i].ff.ss < r / q < all[j].ff.ff / all[j].ff.ss
}
auto cmp2 = [&](int u, int v){
if (x[u] == x[v]) return y[u] < y[v];
return (y[u] - 1.0 * r * x[u] / q) < (y[v] - 1.0 * r * x[v] / q);
// return q * (y[u] - y[v]) < r * (x[u] - x[v]);
};
ff.clear(); pp.clear();
for (int k = i; k < j; k++){
auto [u, v] = all[k].ss;
if (!used[u]){
used[u] = 1;
ff.pb(u);
pp.pb(p[u]);
}
if (!used[v]){
used[v] = 1;
ff.pb(v);
pp.pb(p[v]);
}
}
sort(ff.begin(), ff.end(), cmp2);
sort(pp.begin(), pp.end());
for (int i = 0; i < pp.size(); i++){
p[ff[i]] = pp[i];
T.upd(pp[i], a[ff[i]]);
}
for (int k = i; k < j; k++){
auto [u, v] = all[k].ss;
used[u] = used[v] = 0;
}
out = max(out, T.get());
i = j;
}
cout<<out<<"\n";
}
Compilation message
bulldozer.cpp: In function 'int main()':
bulldozer.cpp:93:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
93 | while (i < all.size()){
| ~~^~~~~~~~~~~~
bulldozer.cpp:95:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
95 | while (j < all.size() && (1LL * all[i].ff.ff * all[j].ff.ss) == (1LL * all[i].ff.ss * all[j].ff.ff)){
| ~~^~~~~~~~~~~~
bulldozer.cpp:100:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
100 | if (j == all.size()){
| ~~^~~~~~~~~~~~~
bulldozer.cpp:133:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
133 | for (int i = 0; i < pp.size(); i++){
| ~~^~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
592 KB |
Output is correct |
| 2 |
Correct |
1 ms |
592 KB |
Output is correct |
| 3 |
Correct |
1 ms |
592 KB |
Output is correct |
| 4 |
Correct |
1 ms |
592 KB |
Output is correct |
| 5 |
Correct |
1 ms |
592 KB |
Output is correct |
| 6 |
Correct |
1 ms |
592 KB |
Output is correct |
| 7 |
Correct |
1 ms |
592 KB |
Output is correct |
| 8 |
Correct |
1 ms |
592 KB |
Output is correct |
| 9 |
Correct |
1 ms |
592 KB |
Output is correct |
| 10 |
Correct |
1 ms |
592 KB |
Output is correct |
| 11 |
Correct |
1 ms |
336 KB |
Output is correct |
| 12 |
Correct |
1 ms |
336 KB |
Output is correct |
| 13 |
Correct |
1 ms |
336 KB |
Output is correct |
| 14 |
Correct |
1 ms |
336 KB |
Output is correct |
| 15 |
Correct |
1 ms |
336 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
3 ms |
848 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
3 ms |
848 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
3 ms |
848 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
592 KB |
Output is correct |
| 2 |
Correct |
1 ms |
592 KB |
Output is correct |
| 3 |
Correct |
1 ms |
592 KB |
Output is correct |
| 4 |
Correct |
1 ms |
592 KB |
Output is correct |
| 5 |
Correct |
1 ms |
592 KB |
Output is correct |
| 6 |
Correct |
1 ms |
592 KB |
Output is correct |
| 7 |
Correct |
1 ms |
592 KB |
Output is correct |
| 8 |
Correct |
1 ms |
592 KB |
Output is correct |
| 9 |
Correct |
1 ms |
592 KB |
Output is correct |
| 10 |
Correct |
1 ms |
592 KB |
Output is correct |
| 11 |
Correct |
1 ms |
336 KB |
Output is correct |
| 12 |
Correct |
1 ms |
336 KB |
Output is correct |
| 13 |
Correct |
1 ms |
336 KB |
Output is correct |
| 14 |
Correct |
1 ms |
336 KB |
Output is correct |
| 15 |
Correct |
1 ms |
336 KB |
Output is correct |
| 16 |
Runtime error |
3 ms |
848 KB |
Execution killed with signal 6 |
| 17 |
Halted |
0 ms |
0 KB |
- |
