//#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#include <bits/stdc++.h>
#define owo(i,a, b) for(int i=(a);i<(b); ++i)
#define uwu(i,a, b) for(int i=(a)-1; i>=(b); --i)
#define senpai push_back
#define ttgl pair<int, int>
#define ayaya cout<<"ayaya~"<<endl
using namespace std;
/*#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<ttgl, null_type,less<ttgl>, rb_tree_tag,tree_order_statistics_node_update>*/
using ll = long long;
using ld = long double;
const ll MOD = 1000000007;
const ll root = 62;
int gcd(int a,int b){return b?gcd(b,a%b):a;}
ll binpow(ll a,ll b){ll res=1;while(b){if(b&1)res=(res*a)%MOD;a=(a*a)%MOD;b>>=1;}return res;}
ll modInv(ll a){return binpow(a, MOD-2);}
const double PI = acos(-1);
const double eps = 1e-6;
const int INF = 0x3f3f3f3f;
const int NINF = 0xc0c0c0c0;
const ll INFLL = 0x3f3f3f3f3f3f3f3f;
const ll NINFLL = 0xc0c0c0c0c0c0c0c0;
const int mxN = 2001;
int n;
//0 = max_prefix; 1 = max_suffix; 2 = realmax; 3 = sum
array<int, 4> sgmax[2*mxN];
array<int, 4> merge(array<int, 4> a, array<int, 4> b) {
array<int, 4> res = {0, 0, 0, 0};
res[0] = max(a[0], a[3] + b[0]);
res[1] = max(b[1], b[3] + a[1]);
res[2] = max({b[2], a[2], a[1] + b[0]});
res[3] = a[3] + b[3];
return res;
}
void upd(int p, int val) {
for(sgmax[p+=n] = {val, val, val, val}; p>1; p>>=1) {
if(p&1) sgmax[p>>1] = merge(sgmax[p^1], sgmax[p]);
else sgmax[p>>1] = merge(sgmax[p], sgmax[p^1]);
}
}
array<int, 4> qmax(int l, int r) {
array<int, 4> left = {0, 0, 0, 0};
array<int, 4> right = {0, 0, 0, 0};
r++;
for(l+=n, r+=n; l<r; l>>=1, r>>=1) {
if(l&1) left = merge(left, sgmax[l++]);
if(r&1) right = merge(sgmax[--r], right);
}
return merge(left, right);
}
struct event{
vector<array<int, 3>> points;
int dx;
int dy;
int inter = 0;
event(int x1, int y1, int x2, int y2, int a1, int a2) {
points.senpai({x1, y1, a1});
points.senpai({x2, y2, a2});
int x = x2-x1;
int y = y2-y1;
int k = gcd(x, y);
x/=k;
y/=k;
if(x<0||(x==0&&y<0)) {
x = -x;
y = -y;
}
dx = x;
dy = y;
//cout<<x<<" "<<y<<'\n';
if(x&&y) {
inter = (-y1*dy)/dx + x1;
}else if(x){
inter = y1;
}else {
inter = x1;
}
}
bool operator<(const event &other) const{
if(dx*other.dy==dy*other.dx) {
return inter<other.inter;
}
return dx*other.dy > dy*other.dx;
}
};
void comb(event &a, event &b) {
if(a.points.size()<b.points.size())swap(a, b);
for(auto p: b.points) {
a.points.senpai(p);
}
sort(a.points.begin(), a.points.end());
a.points.resize(unique(a.points.begin(), a.points.end()) - a.points.begin());
}
map<ttgl, int> mp;
vector<event> all;
array<int, 3> arr[mxN];
int main() {
//freopen("file.in", "r", stdin);
//freopen("file.out", "w", stdout);
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
cin.tie(0)->sync_with_stdio(0);
cin>>n;
owo(i, 0, n) {
cin>>arr[i][0]>>arr[i][1]>>arr[i][2];
}
owo(i, 0, n) {
owo(j, i+1, n) {
all.senpai(event(arr[i][0], arr[i][1], arr[j][0], arr[j][1], arr[i][2], arr[j][2]));
//cout<<arr[i][0]<<" "<<arr[i][1]<<" "<<arr[j][0]<<" "<<arr[j][1]<<" "<<all[all.size()-1].inter<<"\n";
}
}
sort(all.begin(), all.end());
owo(i, 1, all.size()) {
if(all[i-1].dx==all[i].dx&&all[i-1].dy==all[i].dy&&all[i].inter==all[i-1].inter) {
comb(all[i-1], all[i]);
all.erase(all.begin()+i);
i--;
}
}
for(auto e: all) {
sort(e.points.begin(), e.points.end());
reverse(e.points.begin(), e.points.end());
}
sort(arr, arr+n);
owo(i, 0, n) {
upd(i, arr[i][2]);
mp[{arr[i][0], arr[i][1]}] = i;
}
//cout<<qmax(0, n-1)[2]<<"\n";
ll ans = 0;
for(auto e: all) {
//cout<<e.dx<<" "<<e.dy<<"\n";
vector<int> indicies;
for(auto p: e.points) {
indicies.senpai(mp[{p[0], p[1]}]);
}
sort(indicies.begin(), indicies.end());
owo(i, 0, indicies.size()) {
//cout<<indicies[i]<<" ";
upd(indicies[i], e.points[i][2]);
mp[{e.points[i][0], e.points[i][1]}] = indicies[i];
}
//cout<<"\n";
ans = max(ans, qmax(0, n-1)[2]);
}
cout<<ans<<"\n";
return 0;
}
Compilation message
bulldozer.cpp:2: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
2 | #pragma GCC optimization ("O3")
|
bulldozer.cpp:3: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
3 | #pragma GCC optimization ("unroll-loops")
|
bulldozer.cpp: In function 'int main()':
bulldozer.cpp:5:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
5 | #define owo(i,a, b) for(int i=(a);i<(b); ++i)
| ^
bulldozer.cpp:119:5: note: in expansion of macro 'owo'
119 | owo(i, 1, all.size()) {
| ^~~
bulldozer.cpp:5:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
5 | #define owo(i,a, b) for(int i=(a);i<(b); ++i)
| ^
bulldozer.cpp:144:9: note: in expansion of macro 'owo'
144 | owo(i, 0, indicies.size()) {
| ^~~
bulldozer.cpp:150:39: error: no matching function for call to 'max(ll&, std::array<int, 4>::value_type&)'
150 | ans = max(ans, qmax(0, n-1)[2]);
| ^
In file included from /usr/include/c++/9/bits/specfun.h:45,
from /usr/include/c++/9/cmath:1927,
from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:41,
from bulldozer.cpp:4:
/usr/include/c++/9/bits/stl_algobase.h:222:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&)'
222 | max(const _Tp& __a, const _Tp& __b)
| ^~~
/usr/include/c++/9/bits/stl_algobase.h:222:5: note: template argument deduction/substitution failed:
bulldozer.cpp:150:39: note: deduced conflicting types for parameter 'const _Tp' ('long long int' and 'std::array<int, 4>::value_type' {aka 'int'})
150 | ans = max(ans, qmax(0, n-1)[2]);
| ^
In file included from /usr/include/c++/9/bits/specfun.h:45,
from /usr/include/c++/9/cmath:1927,
from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:41,
from bulldozer.cpp:4:
/usr/include/c++/9/bits/stl_algobase.h:268:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::max(const _Tp&, const _Tp&, _Compare)'
268 | max(const _Tp& __a, const _Tp& __b, _Compare __comp)
| ^~~
/usr/include/c++/9/bits/stl_algobase.h:268:5: note: template argument deduction/substitution failed:
bulldozer.cpp:150:39: note: deduced conflicting types for parameter 'const _Tp' ('long long int' and 'std::array<int, 4>::value_type' {aka 'int'})
150 | ans = max(ans, qmax(0, n-1)[2]);
| ^
In file included from /usr/include/c++/9/algorithm:62,
from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:65,
from bulldozer.cpp:4:
/usr/include/c++/9/bits/stl_algo.h:3456:5: note: candidate: 'template<class _Tp> constexpr _Tp std::max(std::initializer_list<_Tp>)'
3456 | max(initializer_list<_Tp> __l)
| ^~~
/usr/include/c++/9/bits/stl_algo.h:3456:5: note: template argument deduction/substitution failed:
bulldozer.cpp:150:39: note: mismatched types 'std::initializer_list<_Tp>' and 'long long int'
150 | ans = max(ans, qmax(0, n-1)[2]);
| ^
In file included from /usr/include/c++/9/algorithm:62,
from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:65,
from bulldozer.cpp:4:
/usr/include/c++/9/bits/stl_algo.h:3462:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::max(std::initializer_list<_Tp>, _Compare)'
3462 | max(initializer_list<_Tp> __l, _Compare __comp)
| ^~~
/usr/include/c++/9/bits/stl_algo.h:3462:5: note: template argument deduction/substitution failed:
bulldozer.cpp:150:39: note: mismatched types 'std::initializer_list<_Tp>' and 'long long int'
150 | ans = max(ans, qmax(0, n-1)[2]);
| ^
