//#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<ll, 4> sgmax[2*mxN];
array<ll, 4> merge(array<ll, 4> a, array<ll, 4> b) {
array<ll, 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, ll 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<ll, 4> qmax(int l, int r) {
array<ll, 4> left = {0, 0, 0, 0};
array<ll, 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;
ll dx;
ll dy;
int a, b;
event(int x1, int y1, int x2, int y2, int a1, int a2, int aa, int bb) {
points.senpai({x1, y1, a1});
points.senpai({x2, y2, a2});
a = aa;
b = bb;
ll x = x2-x1;
ll y = y2-y1;
ll 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';
}
bool operator<(const event &other) const{
return dx*other.dy > dy*other.dx;
}
};
vector<event> all;
array<int, 4> arr[mxN];
int ord[mxN];
int lst[mxN];
int dsu[mxN];
int prv[mxN];
int curr;
int find(int a) {
if(lst[a]!=curr) {
lst[a] = curr;
dsu[a] = a;
}
return a==dsu[a] ? a : dsu[a] = find(dsu[a]);
}
void merge(int a, int b) {
dsu[find(a)] = find(b);
}
bool fix(int a, int b) {
return ord[a]<ord[b];
}
void swapp(int a, int b) {
swap(arr[ord[a]], arr[ord[b]]);
swap(ord[a], ord[b]);
upd(ord[a], arr[ord[a]][2]);
upd(ord[b], arr[ord[b]][2]);
}
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];
arr[i][3] = i;
}
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], i, j));
//cout<<arr[i][0]<<" "<<arr[i][1]<<" "<<arr[j][0]<<" "<<arr[j][1]<<" "<<all[all.size()-1].inter<<"\n";
}
}
//ayaya;
sort(all.begin(), all.end());
sort(arr, arr+n);
owo(i, 0, n) {
upd(i, arr[i][2]);
ord[arr[i][3]] = i;
}
//cout<<qmax(0, n-1)[2]<<"\n";
ll ans = qmax(0, n-1)[2];
for(int i=0; i<all.size(); ) {
int j= i+1;
curr++;
while(j<all.size()&&all[i].dx==all[j].dx&&all[i].dy==all[j].dy)j++;
owo(k, i, j) {
//cout<<all[k].a<<" "<<all[k].b<<endl;
merge(all[k].a, all[k].b);
}
map<int, vector<int>> swp;
owo(k, i, j) {
if(prv[all[k].a]!=curr) {
prv[all[k].a] = curr;
swp[find(all[k].a)].senpai(all[k].a);
}
if(prv[all[k].b]!=curr) {
prv[all[k].b] = curr;
swp[find(all[k].b)].senpai(all[k].b);
}
}
for(auto p: swp) {
vector<int> nodes = p.second;
sort(nodes.begin(), nodes.end(), fix);
int left =0;
int right = nodes.size()-1;
while(left<right) {
swapp(nodes[left++], nodes[right--]);
}
}
ans = max(ans, qmax(0, n-1)[2]);
i = j;
}
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:135:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
135 | for(int i=0; i<all.size(); ) {
| ~^~~~~~~~~~~
bulldozer.cpp:138:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
138 | while(j<all.size()&&all[i].dx==all[j].dx&&all[i].dy==all[j].dy)j++;
| ~^~~~~~~~~~~
bulldozer.cpp:111:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
111 | freopen("file.in", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
