#include <bits/stdc++.h>
using namespace std ;
#define ii pair<int,int>
#define fi first
#define se second
#define vi vector<int>
#define vii vector<ii>
typedef long long ll ;
int n , w[2010] , pos[2010] ;
ll st[10010] , L[10010] , R[10010] , sum[10010] , res = 0 ;
ii pnt[2010], cur ;
pair<ii,int> arr[2010] ;
vector< pair<ii,ii> > srt ;
vector< pair<ii,int> > tmp ;
int gcd(int x,int y){
if(y == 0) return x ;
return gcd(y , x%y );
}
bool slpcmp(ii x, ii y){
if(x.fi == 0 ) return 1 ;
if(y.fi == 0) return 0 ;
if( x.se == 0 && y.se == 0) return 0 ;
if( x.se == 0 ){
if(y.se > 0 )return 1 ;
else return 0 ;
}
else if(y.se == 0){
if(x.se > 0) return 0 ;
else return 1 ;
}
if( (x.se < 0 && y.se < 0) || (x.se > 0 && y.se > 0 ) ) return (double)x.fi / (double)x.se > (double)y.fi / (double) y.se ;
return (double)x.fi / (double)x.se < (double)y.fi / (double) y.se ;
}
bool cmp(pair<ii,ii> x , pair<ii,ii> y){
return slpcmp(x.fi , y.fi) ;
}
bool pntcmp(pair<ii,int> x , pair<ii,int> y){
ll x1 = 1LL * cur.se * x.fi.se - 1LL * cur.fi * x.fi.fi ;
ll x2 = 1LL * cur.se * y.fi.se - 1LL * cur.fi * y.fi.fi ;
if(x1 == x2) return x.fi.se > y.fi.se ;
return x1 > x2 ;
}
bool ycmp(pair<ii,int> x , pair<ii,int> y){
if(x.fi.se == y.fi.se) return x.fi.fi < y.fi.fi ;
return x.fi.se < y.fi.se ;
}
void upd(int node, int f , int l ,int x , ll cst){
if(f == l){
sum[node] = st[node] = cst ;
L[node] = max(0LL , cst) ;
R[node] = max(0LL , cst) ;
return ;
}
int mid = (f+l)>>1 ;
if(x > mid) upd(2*node+1 , mid+1 , l , x, cst) ;
else upd(2*node , f, mid , x ,cst) ;
st[node] = max(st[2*node] , st[2*node+1] ) ;
sum[node] = sum[2*node] + sum[2*node+1] ;
L[node] = max(sum[2*node] + L[2*node+1] , L[2*node] ) ;
R[node] = max(sum[2*node+1] + R[2*node] , R[2*node+1] ) ;
st[node] = max(st[node] , L[2*node+1] + R[2*node] ) ;
}
int main(){
// freopen("in.txt" , "r" , stdin ) ;
// freopen("out.txt" , "w" , stdout) ;
scanf("%d",&n) ;
int a , b , c ;
ii p1, p2 ;
for(int i=1;i<=n;i++){
scanf("%d%d%d",&a,&b,&c) ;
pnt[i] = {a,b} ;
w[i] = c ;
for(int j=1;j<i;j++){
p1 = pnt[i] ; p2 = pnt[j] ;
a = p1.se - p2.se ; b = p1.fi-p2.fi ;
c = gcd(abs(a) , abs(b)) ;
a/=c; b/=c ;
if( a < 0 ) b = -b , a = -a ;
srt.push_back( { {a , b} , {i , j} } ) ;
}
arr[i] = { pnt[i] , i } ;
}
sort( srt.begin() , srt.end() , cmp ) ;
int j , v ;
ll qs = 0 , mn = 0 ;
sort(arr +1 , arr+n+1 , ycmp ) ;
// slope = 0 case
for(int i=1;i<=n;){
j = i ;
while(arr[i].fi.se == arr[j].fi.se && j<=n ) {
// printf("---> %d : %d %d \n", j , arr[j].fi.fi , arr[j].fi.se ) ;
qs+=w[ arr[j].se ];
pos[arr[j].se] = j ;
j++ ;
}
res = max(res , qs - mn) ;
mn = min(mn ,qs) ;
i = j;
}
// printf("mid : %lld\n ", res) ;
for(int i=1;i<=n;i++) upd(1 , 1 , n , pos[i] , w[i] ) ;
j = 0 ;
res = max(res , st[1]) ;
while(srt[j].fi.fi == 0 && j<srt.size() ) j++ ;
// slope != 0 case
pair<ii,int> x , y ;
int f , l ;
ll W ;
for(int i=j ; i<srt.size() ; ){
// printf("\n%d : %d %d %lld \n" , i , srt[i].fi.fi , srt[i].fi.se , res ) ;
j = i ;
cur = srt[i].fi ;
tmp.clear() ;
while(srt[j].fi == cur && j<srt.size() ) {
v = srt[j].se.fi ;
tmp.push_back({ pnt[v] , srt[j].se.fi}) ;
v = srt[j].se.se ;
tmp.push_back({ pnt[v] , srt[j].se.se}) ;
j++ ;
}
sort( tmp.begin() , tmp.end() , pntcmp ) ;
tmp.resize(unique(tmp.begin() , tmp.end() ) - tmp.begin() ) ;
i = j ;
for(int k=0;k<tmp.size();){
j = k ;
f = 1e9 , l = 0 ;
W = 0 ;
x = tmp[k] , y = tmp[j] ;
ll x1 = 1LL * cur.se * x.fi.se - 1LL * cur.fi * x.fi.fi ;
ll x2 = 1LL * cur.se * y.fi.se - 1LL * cur.fi * y.fi.fi ;
while(x2 == x1 && j<tmp.size()){
y = tmp[j] ;
f = min(pos[y.se] , f) ;
l = max(pos[y.se] , l) ;
x2 = 1LL * cur.se * y.fi.se - 1LL * cur.fi * y.fi.fi ;
// upd segtree ;
upd(1 , 1 , n , pos[y.se] , 0 ) ;
// combine points ;
W += w[y.se] ;
// printf("%d : %d %d %d %d %d %d %d\n", j , y.fi.fi , y.fi.se , y.se , pos[y.se] , W , f , l) ;
j++ ;
y = tmp[j] ;
x2 = 1LL * cur.se * y.fi.se - 1LL * cur.fi * y.fi.fi ;
}
sort( arr+f , arr+l+1 , pntcmp ) ;
// upd at f with W ;
upd(1 , 1, n, f , W ) ;
// printf("---> %d %d\n" , f, l ) ;
for(int ptr=f;ptr<=l;ptr++) pos[arr[ptr].se] = ptr ;
k = j ;
}
// find res
res = max(res , st[1]) ;
// upd again
for(int k=0;k<tmp.size();k++){
// upd at new pos ;
v = tmp[k].se ;
upd( 1 , 1 , n , pos[v] , w[v] ) ;
}
res = max(res , st[1]) ;
}
printf("%lld\n", res) ;
}
Compilation message
bulldozer.cpp: In function 'int main()':
bulldozer.cpp:114:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(srt[j].fi.fi == 0 && j<srt.size() ) j++ ;
~^~~~~~~~~~~
bulldozer.cpp:119:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=j ; i<srt.size() ; ){
~^~~~~~~~~~~
bulldozer.cpp:125:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(srt[j].fi == cur && j<srt.size() ) {
~^~~~~~~~~~~
bulldozer.cpp:137:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int k=0;k<tmp.size();){
~^~~~~~~~~~~
bulldozer.cpp:144:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(x2 == x1 && j<tmp.size()){
~^~~~~~~~~~~
bulldozer.cpp:170:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int k=0;k<tmp.size();k++){
~^~~~~~~~~~~
bulldozer.cpp:76:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&n) ;
~~~~~^~~~~~~~~
bulldozer.cpp:80:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d",&a,&b,&c) ;
~~~~~^~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3 ms |
896 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
640 KB |
Output is correct |
| 2 |
Correct |
6 ms |
612 KB |
Output is correct |
| 3 |
Correct |
6 ms |
612 KB |
Output is correct |
| 4 |
Correct |
6 ms |
640 KB |
Output is correct |
| 5 |
Correct |
5 ms |
512 KB |
Output is correct |
| 6 |
Correct |
6 ms |
512 KB |
Output is correct |
| 7 |
Correct |
6 ms |
560 KB |
Output is correct |
| 8 |
Correct |
5 ms |
512 KB |
Output is correct |
| 9 |
Correct |
5 ms |
512 KB |
Output is correct |
| 10 |
Correct |
5 ms |
512 KB |
Output is correct |
| 11 |
Runtime error |
3 ms |
512 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 12 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
640 KB |
Output is correct |
| 2 |
Correct |
6 ms |
612 KB |
Output is correct |
| 3 |
Correct |
6 ms |
612 KB |
Output is correct |
| 4 |
Correct |
6 ms |
640 KB |
Output is correct |
| 5 |
Correct |
5 ms |
512 KB |
Output is correct |
| 6 |
Correct |
6 ms |
512 KB |
Output is correct |
| 7 |
Correct |
6 ms |
560 KB |
Output is correct |
| 8 |
Correct |
5 ms |
512 KB |
Output is correct |
| 9 |
Correct |
5 ms |
512 KB |
Output is correct |
| 10 |
Correct |
5 ms |
512 KB |
Output is correct |
| 11 |
Runtime error |
3 ms |
512 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 12 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
640 KB |
Output is correct |
| 2 |
Correct |
6 ms |
612 KB |
Output is correct |
| 3 |
Correct |
6 ms |
612 KB |
Output is correct |
| 4 |
Correct |
6 ms |
640 KB |
Output is correct |
| 5 |
Correct |
5 ms |
512 KB |
Output is correct |
| 6 |
Correct |
6 ms |
512 KB |
Output is correct |
| 7 |
Correct |
6 ms |
560 KB |
Output is correct |
| 8 |
Correct |
5 ms |
512 KB |
Output is correct |
| 9 |
Correct |
5 ms |
512 KB |
Output is correct |
| 10 |
Correct |
5 ms |
512 KB |
Output is correct |
| 11 |
Runtime error |
3 ms |
512 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 12 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3 ms |
896 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
