Submission #27063

#	Time	Username	Problem	Language	Result	Execution time	Memory
27063		noobprogrammer	Bulldozer (JOI17_bulldozer)	C++14	0 / 100	6 ms	896 KiB

bulldozer

#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  
	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.erase(unique(tmp.begin() , tmp.end() ) , tmp.end() ) ;
		i = j ;
		
		for(int k=0;k<tmp.size();){
			j = k ;
			int f = 1e9 , l = 0 , W = 0 ;
			pair<ii,int> 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 (stderr)

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:116:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=j ; i<srt.size() ; ){
                ~^~~~~~~~~~~
bulldozer.cpp:122:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(srt[j].fi == cur && j<srt.size() ) {
                             ~^~~~~~~~~~~
bulldozer.cpp:134:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int k=0;k<tmp.size();){
               ~^~~~~~~~~~~
bulldozer.cpp:140:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    while(x2 == x1 && j<tmp.size()){
                      ~^~~~~~~~~~~
bulldozer.cpp:166: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) ;
   ~~~~~^~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 5
• Subtask 2: 0 / 20
• Subtask 3: 0 / 35
• Subtask 4: 0 / 20
• Subtask 5: 0 / 20