oj.uz

Submission #27068

# Submission time Handle Problem Language Result Execution time Memory
27068 2017-07-09T06:55:06 Z noobprogrammer Bulldozer (JOI17_bulldozer) C++14
20 / 100
 2000 ms 31964 KB 
#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] , sz = 0 ;
ll st[10010] , L[10010] , R[10010] , sum[10010] , res = 0 ;
ii pnt[2010], cur ;
pair<ii,int> arr[2010] ;
pair<ii,ii> srt[4000010] ;
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[sz] = { {a , b} , {i , j} }  ;
			sz++ ;
		}
		arr[i] = { pnt[i] , i } ;
	}
	sort( srt , srt + sz , 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<sz ) j++ ;
	// slope != 0 case  
	pair<ii,int> x , y  ;
	int f , l ;
	ll W ;
	for(int i=j ; i<sz ; ){
		// 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<sz ) {
			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:138:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int k=0;k<tmp.size();){
               ~^~~~~~~~~~~
bulldozer.cpp:145:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    while(x2 == x1 && j<tmp.size()){
                      ~^~~~~~~~~~~
bulldozer.cpp:171: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.0

# Verdict Execution time Memory Grader output
1 Runtime error 32 ms 760 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 6 ms 384 KB Output is correct
3 Correct 6 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 6 ms 384 KB Output is correct
7 Correct 5 ms 428 KB Output is correct
8 Correct 5 ms 512 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 2 ms 384 KB Output is correct
13 Correct 2 ms 384 KB Output is correct
14 Correct 2 ms 384 KB Output is correct
15 Correct 2 ms 356 KB Output is correct
16 Correct 2 ms 512 KB Output is correct
17 Correct 2 ms 384 KB Output is correct
18 Correct 2 ms 384 KB Output is correct
19 Correct 2 ms 384 KB Output is correct
20 Correct 2 ms 384 KB Output is correct
21 Correct 5 ms 512 KB Output is correct
22 Correct 5 ms 384 KB Output is correct
23 Correct 5 ms 384 KB Output is correct
24 Correct 5 ms 384 KB Output is correct
25 Correct 5 ms 384 KB Output is correct
26 Correct 5 ms 432 KB Output is correct
27 Correct 5 ms 384 KB Output is correct
28 Correct 5 ms 432 KB Output is correct
29 Correct 5 ms 384 KB Output is correct
30 Correct 5 ms 384 KB Output is correct
31 Correct 5 ms 484 KB Output is correct
32 Correct 6 ms 384 KB Output is correct

Subtask #3
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 6 ms 384 KB Output is correct
3 Correct 6 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 6 ms 384 KB Output is correct
7 Correct 5 ms 428 KB Output is correct
8 Correct 5 ms 512 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 2 ms 384 KB Output is correct
13 Correct 2 ms 384 KB Output is correct
14 Correct 2 ms 384 KB Output is correct
15 Correct 2 ms 356 KB Output is correct
16 Correct 2 ms 512 KB Output is correct
17 Correct 2 ms 384 KB Output is correct
18 Correct 2 ms 384 KB Output is correct
19 Correct 2 ms 384 KB Output is correct
20 Correct 2 ms 384 KB Output is correct
21 Correct 5 ms 512 KB Output is correct
22 Correct 5 ms 384 KB Output is correct
23 Correct 5 ms 384 KB Output is correct
24 Correct 5 ms 384 KB Output is correct
25 Correct 5 ms 384 KB Output is correct
26 Correct 5 ms 432 KB Output is correct
27 Correct 5 ms 384 KB Output is correct
28 Correct 5 ms 432 KB Output is correct
29 Correct 5 ms 384 KB Output is correct
30 Correct 5 ms 384 KB Output is correct
31 Correct 5 ms 484 KB Output is correct
32 Correct 6 ms 384 KB Output is correct
33 Execution timed out 2029 ms 31964 KB Time limit exceeded
34 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 6 ms 384 KB Output is correct
3 Correct 6 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 6 ms 384 KB Output is correct
7 Correct 5 ms 428 KB Output is correct
8 Correct 5 ms 512 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 2 ms 384 KB Output is correct
13 Correct 2 ms 384 KB Output is correct
14 Correct 2 ms 384 KB Output is correct
15 Correct 2 ms 356 KB Output is correct
16 Correct 2 ms 512 KB Output is correct
17 Correct 2 ms 384 KB Output is correct
18 Correct 2 ms 384 KB Output is correct
19 Correct 2 ms 384 KB Output is correct
20 Correct 2 ms 384 KB Output is correct
21 Correct 5 ms 512 KB Output is correct
22 Correct 5 ms 384 KB Output is correct
23 Correct 5 ms 384 KB Output is correct
24 Correct 5 ms 384 KB Output is correct
25 Correct 5 ms 384 KB Output is correct
26 Correct 5 ms 432 KB Output is correct
27 Correct 5 ms 384 KB Output is correct
28 Correct 5 ms 432 KB Output is correct
29 Correct 5 ms 384 KB Output is correct
30 Correct 5 ms 384 KB Output is correct
31 Correct 5 ms 484 KB Output is correct
32 Correct 6 ms 384 KB Output is correct
33 Execution timed out 2029 ms 31964 KB Time limit exceeded
34 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 32 ms 760 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -