#include "bits/stdc++.h"
using namespace std;
#define ar array
const int N = 2005;
long double const eps = 1e-16;
struct ST{
ar<long long, 4> tree[N * 4];
void merge(ar<long long, 4>& x, ar<long long, 4>& a, ar<long long, 4>& b){
x[0] = max({a[0], b[0], a[2] + b[1]});
x[1] = max({a[1], a[3] + b[1]});
x[2] = max({b[2], b[3] + a[2]});
x[3] = a[3] + b[3];
}
void sett(int i, int v, int lx = 0, int rx = N, int x = 1){
if(lx == rx){
tree[x] = {max(v, 0), max(v, 0), max(v, 0), v}; return;
} int m = (lx + rx) >> 1;
if(i <= m) sett(i, v, lx, m, x<<1);
else sett(i, v, m+1, rx, x<<1|1);
merge(tree[x], tree[x<<1], tree[x<<1|1]);
}
}tree;
/*
5
5 1 5
4 2 2
3 3 -2
2 4 3
1 5 -1
6
2 2 10
4 1 10
5 2 10
2 5 10
4 4 -5
5 5 10
*/
long long res;
bool operator < (pair<pair<int, int>, pair<int, int>>& a, pair<pair<int, int>, pair<int, int>>& b){
return (a.first.first * 1ll * b.first.second < b.first.first * 1ll * a.first.second);
}
void check(vector<ar<int, 3>>& a, int n){
sort(a.begin(), a.end(), [&](auto& a, auto& b){
if(a[0] != b[0]) return a[0] < b[0];
return a[1] > b[1];
});
vector<pair<pair<int, int>, pair<int, int>>> tt;
for(int i=0;i<n;i++){
for(int j=i+1;j<n;j++){
if(a[i][0] == a[j][0]) continue;
tt.push_back({{a[j][1] - a[i][1], a[i][0] - a[j][0]}, {i, j}});
}
} vector<int> pos(n), used(n);
for(int i=0;i<n;i++) pos[i] = i, tree.sett(i, a[i][2]);
res = max(res, tree.tree[1][0]);
sort(tt.begin(), tt.end()); //{
for(int l=0;l<(int)tt.size();){
int k = l;
while(k < (int)tt.size() && !(tt[l] < tt[k])){
auto [i, j] = tt[k].second; k++;
swap(pos[i], pos[j]);
tree.sett(pos[i], a[i][2]),
tree.sett(pos[j], a[j][2]);
} while(l < k) used[tt[l].second.first] = used[tt[l].second.second] = 0, l++;
res = max(res, tree.tree[1][0]);
}
}
signed main(){
ios::sync_with_stdio(0); cin.tie(0);
int n; cin>>n;
vector<ar<int, 3>> a(n);
for(int i=0;i<n;i++){
cin>>a[i][0]>>a[i][1]>>a[i][2];
}
check(a, n);
for(auto& x : a) swap(x[0], x[1]);
check(a, n);
cout<<res<<"\n";
}
Compilation message
bulldozer.cpp: In function 'void check(std::vector<std::array<int, 3> >&, int)':
bulldozer.cpp:72:9: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
72 | auto [i, j] = tt[k].second; k++;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
460 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
508 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
508 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
508 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
460 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
