#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld ;
typedef pair <ll,ll> pll ;
#define eb emplace_back
#define all(x) (x).begin(),(x).end()
#define MAXN 5003
const ll llinf = 0x3f3f3f3f3f3f3f3f;
struct po {
ll x,y;
ll co;
bool operator <(po &r) {
return pll(x,y) < pll(r.x,r.y);
}
} arr[MAXN];
struct line {
ll i,j;
long double a;
line(int i,int j,ld a):i(i),j(j),a(a) {}
bool operator<(line &r) {
return a>r.a;
}
};
vector <line> larr;
ll N;
struct node {
ll lsum,rsum,sum,ans;
node() {
lsum = rsum = sum = ans =0 ;
}
node(ll l,ll r,ll s,ll a) {
lsum = l;
rsum =r;
sum =s ;
ans = a;
}
};
struct seg {
node tree[5003*4];
node merge(node l,node r) {
node ret;
ret.lsum = max(l.lsum,l.sum + r.lsum);
ret.rsum = max(r.rsum,l.rsum + r.sum);
ret.sum = l.sum + r.sum;
ret.ans = max({l.ans,r.ans,ret.sum,l.rsum + r.lsum});
return ret;
}
node query(ll nodE,ll ns,ll ne,ll s,ll e) {
if(e<ns || ne <s )
return node(0,0,0,0);
if(s<=ns &&ne <=e)
return tree[nodE];
return merge(query(nodE*2,ns,ns + ne >>1,s,e),query(nodE*2+1,(ns+ne>>1) + 1,ne,s,e));
}
void update(ll nodE,ll ns,ll ne,ll id,node k) {
if(ne < id || id < ns)
return;
if(ns == ne) {
tree[nodE] = k;
return ;
}
update(nodE*2,ns,(ns+ne)/2,id,k);
update(nodE*2+1,(ns+ne)/2+1,ne,id,k);
tree[nodE] = merge(tree[nodE*2],tree[nodE*2+1]);
}
} SEG;
int ind[5003];
int main() {
scanf("%lld",&N);
for(ll i=1; i<=N; i++)
scanf("%lld %lld %lld", &arr[i].x,&arr[i].y,&arr[i].co);
sort(arr+1,arr+1+N);
for(ll i=1; i<=N; i++) {
for(ll j=i+1; j<=N; j++) {
long double deltax = (ld)arr[i].x - arr[j].x;
long double deltay = (ld)arr[i].y - arr[j].y;
if(deltax==0)
deltay = deltax>=0? 1e-18 : -1e-18;
larr.eb(i,j,deltay/deltax);
}
}
sort(larr.begin(),larr.end());
for(ll i=1; i<=N; i++) {
ll C = arr[i].co;
SEG.update(1,1,N,i,node(C,C,C,C));
}
ll res = SEG.query(1,1,N,1,N).ans;
for(int i=1; i<=N; i++)
ind[i] =i ;
for(int i=0; i<larr.size(); i++) {
int e;
for(int j=i; j<larr.size(); j++) {
if(larr[i].a == larr[j].a)
e = j;
else
break;
}
for(int j = i ; j<=e; j++) {
auto it = larr[j];
ll l = it.i, r = it.j ;
node x = SEG.query(1,1,N,ind[l],ind[l]);
node y = SEG.query(1,1,N,ind[r],ind[r]);
SEG.update(1,1,N,ind[r],x);
SEG.update(1,1,N,ind[l],y);
swap(ind[l],ind[r]);
}
res = max(res,SEG.query(1,1,N,1,N).ans);
i=e;
}
printf("%lld",res);
}
Compilation message
bulldozer.cpp: In member function 'node seg::query(ll, ll, ll, ll, ll)':
bulldozer.cpp:56:41: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
return merge(query(nodE*2,ns,ns + ne >>1,s,e),query(nodE*2+1,(ns+ne>>1) + 1,ne,s,e));
~~~^~~~
bulldozer.cpp:56:73: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
return merge(query(nodE*2,ns,ns + ne >>1,s,e),query(nodE*2+1,(ns+ne>>1) + 1,ne,s,e));
~~^~~
bulldozer.cpp: In function 'int main()':
bulldozer.cpp:93:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<larr.size(); i++) {
~^~~~~~~~~~~~
bulldozer.cpp:95:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j=i; j<larr.size(); j++) {
~^~~~~~~~~~~~
bulldozer.cpp:72:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld",&N);
~~~~~^~~~~~~~~~~
bulldozer.cpp:74:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld %lld %lld", &arr[i].x,&arr[i].y,&arr[i].co);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bulldozer.cpp:94:13: warning: 'e' may be used uninitialized in this function [-Wmaybe-uninitialized]
int e;
^
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
5 ms |
1272 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
6 ms |
1528 KB |
Output is correct |
| 2 |
Correct |
6 ms |
1532 KB |
Output is correct |
| 3 |
Correct |
6 ms |
1272 KB |
Output is correct |
| 4 |
Correct |
6 ms |
1400 KB |
Output is correct |
| 5 |
Correct |
6 ms |
1400 KB |
Output is correct |
| 6 |
Correct |
6 ms |
1400 KB |
Output is correct |
| 7 |
Correct |
6 ms |
1420 KB |
Output is correct |
| 8 |
Correct |
5 ms |
1400 KB |
Output is correct |
| 9 |
Correct |
5 ms |
1400 KB |
Output is correct |
| 10 |
Correct |
5 ms |
1300 KB |
Output is correct |
| 11 |
Incorrect |
3 ms |
1016 KB |
Output isn't correct |
| 12 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
6 ms |
1528 KB |
Output is correct |
| 2 |
Correct |
6 ms |
1532 KB |
Output is correct |
| 3 |
Correct |
6 ms |
1272 KB |
Output is correct |
| 4 |
Correct |
6 ms |
1400 KB |
Output is correct |
| 5 |
Correct |
6 ms |
1400 KB |
Output is correct |
| 6 |
Correct |
6 ms |
1400 KB |
Output is correct |
| 7 |
Correct |
6 ms |
1420 KB |
Output is correct |
| 8 |
Correct |
5 ms |
1400 KB |
Output is correct |
| 9 |
Correct |
5 ms |
1400 KB |
Output is correct |
| 10 |
Correct |
5 ms |
1300 KB |
Output is correct |
| 11 |
Incorrect |
3 ms |
1016 KB |
Output isn't correct |
| 12 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
6 ms |
1528 KB |
Output is correct |
| 2 |
Correct |
6 ms |
1532 KB |
Output is correct |
| 3 |
Correct |
6 ms |
1272 KB |
Output is correct |
| 4 |
Correct |
6 ms |
1400 KB |
Output is correct |
| 5 |
Correct |
6 ms |
1400 KB |
Output is correct |
| 6 |
Correct |
6 ms |
1400 KB |
Output is correct |
| 7 |
Correct |
6 ms |
1420 KB |
Output is correct |
| 8 |
Correct |
5 ms |
1400 KB |
Output is correct |
| 9 |
Correct |
5 ms |
1400 KB |
Output is correct |
| 10 |
Correct |
5 ms |
1300 KB |
Output is correct |
| 11 |
Incorrect |
3 ms |
1016 KB |
Output isn't correct |
| 12 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
5 ms |
1272 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
