We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
fromcollectionsimportnamedtuplefrombisectimportbisect_leftimportsysPlace=namedtuple('Place','lat,long,height,points')chunkplaces={}#placesgetinsertedintolistscontainedhere,groupedbykeysoftheirlocationschunkvals={}#holdsvaluesgiant=Falsedefgetkey(place,off_lat=0,off_long=0):return((place.lat// d_lat + off_lat) * 200011) + place.long // d_long + off_long # unique for n<=200000defrecordvalue(place,val):ifval<0:return#notworthgoinghere;noneedtotrackkey=getkey(place)ifkeynotinchunkplaces:chunkplaces[key]=[]chunkvals[key]=[]ifgiant:iflen(chunkvals[key])==0:chunkvals[key].append(-val)chunkplaces[key].append(place)else:ifval<-chunkvals[key][0]:returnelse:chunkvals[key][0]=-valchunkplaces[key][0]=placeelse:i=bisect_left(chunkvals[key],-val)chunkplaces[key].insert(i,place)chunkvals[key].insert(i,-val)# print(i, val, [val for val in chunkvals[key]])defgetbestinchunk(place,key,best):# find best suitable match in chunkifkeynotinchunkvals:return0fori,(cand,val)inenumerate(zip(chunkplaces[key],chunkvals[key])):# print("evaluating %s"%cand)if-val<best:# this is the best we have, but it's not as good as we've seen other places; abortreturn0ifabs(place.lat-cand.lat)<=d_lat \
andabs(place.long-cand.long)<=d_long:# and cand.height > place.height: # height is given, assuming they're unique# suitable, return itreturn-val# no suitable matchreturn0defgetbest(place):# find best match in this and neighboring chunks, then pick the bestbest=0#alwayshavetheoptiontostophereforiin[0,1,-1]:forjin[0,1,-1]:key=getkey(place,i,j)ret=getbestinchunk(place,key,best)ifret>best:best=retreturnbestdefcalculatevalue(place):val=place.points+getbest(place)recordvalue(place,val)returnvalif__name__=="__main__":n,d_lat,d_long=input().strip().split(' ')n,d_lat,d_long=[int(n),int(d_lat),int(d_long)]places=[]ifd_lat==200000:giant=Truefora0inrange(n):latitude,longitude,height,points=input().strip().split(' ')latitude,longitude,height,points=[int(latitude),int(longitude),int(height),int(points)]places.append(Place(latitude,longitude,height,points))places.sort(key=lambdap:-p.height)#computehighestfirstbest=0forpinplaces:ret=calculatevalue(p)ifret>best:best=retprint(best)
Maximizing Mission Points
You are viewing a single comment's thread. Return to all comments →