Maximizing Mission Points


Problem Statement :


Xander Cage has a list of cities he can visit on his new top-secret mission. He represents each city as a tuple of . The values of , , and  are distinct across all cities.

We define a mission as a sequence of cities, , that he visits. We define the total  of such a mission to be the sum of the  of all the cities in his mission list.

Being eccentric, he abides by the following rules on any mission:

He can choose the number of cities he will visit (if any).
He can start the mission from any city.
He visits cities in order of strictly increasing .
The absolute difference in  between adjacent visited cities in his mission must be at most .
The absolute difference in  between adjacent visited cities in his mission must be at most .
Given , , and the definitions for  cities, find and print the maximum possible total  that Xander can earn on a mission.

Input Format

The first line contains three space-separated integers describing the respective values of , , and .
Each line  of the  subsequent lines contains four space-separated integers denoting the respective , , , and  for a city.

Constraints

Output Format

Print a single integer denoting the maximum possible  that Xander can earn on a mission.



Solution :



title-img


                            Solution in C :

In  C  :







#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct _tree{
  int *y;
  long long *a;
  int size;
  int N;
  int *left_idx;
  int *right_idx;
} tree;
int diff(int x,int y);
long long max(long long x,long long y);
void init(int n,int *N);
long long range_sum( int i, int j);
void updatea(int i);
void build(int v);
void merge(tree *t,tree *x,tree *y);
int get_i(int*a,int num,int size);
int med(int*a,int size);
long long query(int v);
void update(int v,int idx);
int x1,x2,y1,y2,N,tl[800000],tr[800000];
long long val,*tt;
int lat[200000]={0},lon[200000]={0},poi[200000],tla[200000]={0};
tree t[800000];

int main(){
  int n,x,y,c,i,j,max_idx=-1,a,b,C,d;
  long long max=0,dp;
  scanf("%d%d%d",&n,&x,&y);
  for(i=c=0;i<n;i++){
    scanf("%d%d%d%d",&a,&b,&C,&d);
    if(d>0)
      c++;
    lat[C-1]=a;
    lon[C-1]=b;
    poi[C-1]=d;
    tla[a-1]=b;
  }
  if(!c){
    printf("0");
    return 0;
  }
  tl[1]=0;
  tr[1]=199999;
  build(1);
  for(i=199999;i>=0;i--)
    if(lat[i]){
      if(max_idx!=-1 && diff(lat[max_idx],lat[i])<=x && diff(lon[max_idx],lon[i])<=y)
        dp=max;
      else{
        x1=lat[i]-x-1;
        x2=lat[i]+x-1;
        y1=lon[i]-y;
        y2=lon[i]+y;
        dp=query(1);
      }
      if(dp>0)
        dp+=poi[i];
      else
        dp=poi[i];
      if(dp>max){
        max=dp;
        max_idx=i;
      }
      if(dp>0){
        x1=lat[i]-1;
        y1=lon[i];
        val=dp;
        update(1,-1);
      }
    }
  printf("%lld",max);
  return 0;
}
int diff(int x,int y){
  return (x<y)?(y-x):(x-y);
}
long long max(long long x,long long y){
  return (x>y)?x:y;
}
void init(int n,int *N){
  (*N) = 1;
  while( (*N) < n ) (*N) *= 2;
}
long long range_sum( int i, int j){
  long long ans = 0;
  for( i += N, j += N; i <= j; i = ( i + 1 ) / 2, j = ( j - 1 ) / 2 )
  {
    if( i % 2 == 1 ) ans = max(ans,tt[i]);
    if( j % 2 == 0 ) ans = max(ans,tt[j]);
  }
  return ans;
}
void updatea(int i){
  int j;
  for( j = i + N; j; j /= 2 ) tt[j] = max(tt[j],val);
}
void build(int v){
  if(tl[v]==tr[v]){
    t[v].size=1;
    t[v].y=(int*)malloc(t[v].size*sizeof(int));
    t[v].a=(long long*)malloc(4*t[v].size*sizeof(long long));
    memset(t[v].a,0,4*t[v].size*sizeof(long long));
    t[v].y[0]=tla[tl[v]];
    init(t[v].size,&t[v].N);
  }
  else{
    int tm=(tl[v]+tr[v])/2;
    tl[2*v]=tl[v];
    tl[2*v+1]=tm+1;
    tr[2*v]=tm;
    tr[2*v+1]=tr[v];
    build(v*2);
    build(v*2+1);
    merge(&t[v],&t[v*2],&t[v*2+1]);
  }
  return;
}
void merge(tree *t,tree *x,tree *y){
  int i=0,j=0;
  t->size=x->size+y->size;
  t->y=(int*)malloc(t->size*sizeof(int));
  t->left_idx=(int*)malloc(t->size*sizeof(int));
  t->right_idx=(int*)malloc(t->size*sizeof(int));
  t->a=(long long*)malloc(t->size*sizeof(long long)*4);
  memset(t->a,0,t->size*sizeof(long long)*4);
  init(t->size,&t->N);
  while(i<x->size || j<y->size){
    if(i==x->size){
      t->y[i+j]=y->y[j];
      t->left_idx[i+j]=i-1;
      t->right_idx[i+j]=j;
      j++;
    } 
    else if(j==y->size){
      t->y[i+j]=x->y[i];
      t->left_idx[i+j]=i;
      t->right_idx[i+j]=j-1;
      i++;
    }
    else if(x->y[i]<=y->y[j]){
      t->y[i+j]=x->y[i];
      t->left_idx[i+j]=i;
      t->right_idx[i+j]=j-1;
      i++;
    } 
    else{
      t->y[i+j]=y->y[j];
      t->left_idx[i+j]=i-1;
      t->right_idx[i+j]=j;
      j++;
    }
  }
  return;
}
int get_i(int*a,int num,int size){
  if(size==0)
    return 0;
  if(num>med(a,size))
    return get_i(&a[(size+1)>>1],num,size>>1)+((size+1)>>1);
  else
    return get_i(a,num,(size-1)>>1);
}
int med(int*a,int size){
  return a[(size-1)>>1];
}
long long query(int v){
  int i,j;
  if(tl[v]>x2 || tr[v]<x1 || !t[v].a[1])
    return 0;
  if(tl[v]>=x1 && tr[v]<=x2){
    i=get_i(t[v].y,y1,t[v].size);
    j=get_i(t[v].y,y2+1,t[v].size)-1;
    if(j<i)
      return 0;
    N=t[v].N;
    tt=t[v].a;
    return range_sum(i,j);
  }
  else if(tl[v]!=tr[v])
    return max(query(2*v),query(2*v+1));
  return 0;
}
void update(int v,int idx){
  if(tl[v]<=x1 && tr[v]>=x1){
    if(idx==-1)
      idx=get_i(t[v].y,y1,t[v].size);
    N=t[v].N;
    tt=t[v].a;
    updatea(idx);
    if(tl[v]!=tr[v]){
      update(v*2,t[v].left_idx[idx]);
      update(v*2+1,t[v].right_idx[idx]);
    }
  }
  return;
}
                        


                        Solution in C++ :

In  C++  :





//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define fst first
#define snd second
#define forn(i, n) for (int i = 0; i < int(n); ++i)
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vll;
typedef pair<int, int> pii;
typedef vector<pii> vii;
#define sz(c) (int)(c).size()
#define ALL(c) (c).begin(), (c).end()

struct town
{
    int x, y, h, p;

    bool operator < (const town &o) const
    {
        return h < o.h;
    }
};

struct segtree
{
    vll vals;
    int tsz;

    segtree ()
    {
        vals.clear();
        tsz = 0;
    }

    segtree (int n)
    {
        tsz = 1;
        while (tsz <= n)
            tsz *= 2;

        vals.assign(2 * tsz, 0);
    }

    void put (int pos, ll what)
    {
        for (pos += tsz; pos > 0; pos >>= 1)
            vals[pos] = max(vals[pos], what);
    }

    ll query (int l, int r)
    {
        ll ans = 0;
        for (l += tsz, r += tsz; l < r; l >>= 1, r >>= 1)
        {
            if (l & 1)
                ans = max(ans, vals[l++]);
            if (r & 1)
                ans = max(ans, vals[--r]);
        }
        return ans;
    }
};

struct segtree2d
{
    vvi who;
    vector<segtree> data;
    int tsz;

    segtree2d (const vii &ps)
    {
        int X = 0;
        const int n = sz(ps);
        forn (i, n) X = max(X, ps[i].fst);

        tsz = 1;
        while (tsz <= X)
            tsz *= 2;

        data.resize(2 * tsz);
        who.resize(2 * tsz);
        forn (i, n)
            who[ps[i].fst + tsz].pb(ps[i].snd);

        for (int i = tsz; i < 2 * tsz; i++)
            data[i] = segtree(sz(who[i]));

        for (int i = tsz - 1; i >= 1; i--)
        {
            who[i].resize(sz(who[2 * i]) + sz(who[2 * i + 1]));
            merge(ALL(who[2 * i]), ALL(who[2 * i + 1]), who[i].begin());
            data[i] = segtree(sz(who[i]));
        }
    }

    ll query (int v, int d, int u)
    {
        int rd = lower_bound(ALL(who[v]), d) - who[v].begin();
        int ru = lower_bound(ALL(who[v]), u) - who[v].begin();
        return data[v].query(rd, ru);
    }

    ll query (int l, int r, int d, int u)
    {
        r = min(r, tsz);
        ll ans = 0;
        for (l += tsz, r += tsz; l < r; l >>= 1, r >>= 1)
        {
            if (l & 1)
                ans = max(ans, query(l++, d, u));
            if (r & 1)
                ans = max(ans, query(--r, d, u));
        }
        return ans;
    }

    void putnode (int v, int pos, ll what)
    {
        int cur = lower_bound(ALL(who[v]), pos) - who[v].begin();
        assert(cur != sz(who[v]) && who[v][cur] == pos);
        data[v].put(cur, what);
    }

    void put (int x, int y, ll what)
    {
        for (x += tsz; x > 0; x >>= 1)
            putnode(x, y, what);
    }
};

void solve (int n)
{
    int mx, my;
    cin >> mx >> my;

    vector<town> v(n);
    forn (i, n)
        cin >> v[i].x >> v[i].y >> v[i].h >> v[i].p;

    sort(ALL(v));
    vii ps(n);
    forn (i, n) ps[i] = mp(v[i].x, v[i].y);

    segtree2d data(ps);
    vll dp(n);

    forn (i, n)
    {
        int cx = v[i].x, cy = v[i].y;
        int lx = max(0, cx - mx), ly = max(0, cy - my);
        int rx = cx + mx, ry = cy + my;
        dp[i] = data.query(lx, rx + 1, ly, ry + 1) + v[i].p;
        data.put(cx, cy, dp[i]);
    }

    ll ans = max(0LL, *max_element(ALL(dp)));
    cout << ans << endl;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n;
    while (cin >> n)
        solve(n);
}
                    


                        Solution in Java :

In  Java :








import java.io.ByteArrayInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.InputMismatchException;

public class D {
	InputStream is;
	PrintWriter out;
	String INPUT = "";
	
	void solve()
	{
		int n = ni();
		int x = ni(), y = ni();
		int[][] co = new int[n][];
		for(int i = 0;i < n;i++){
			co[i] = new int[]{ni(), ni(), ni(), ni()};
		}
//		Arrays.sort(co, new Comparator<int[]>() {
//			public int compare(int[] a, int[] b) {
//				return a[2] - b[2];
//			}
//		});
		StaticRangeTreeRMQ2 st = new StaticRangeTreeRMQ2(co, 200005);
//		for(int i = 0;i < n;i++){
//			st.update(co[i][0], co[i][1], Long.MAX_VALUE / 2);
//		}
		mergesort(co, 0, n);
		long max = Long.MIN_VALUE;
		long[] dp = new long[n];
		for(int i = 0;i < n;i++){
			long min = -st.min(co[i][0]-x, co[i][0]+x+1, co[i][1]-y, co[i][1]+y+1);
			long val = co[i][3] + Math.max(min, 0);
			dp[i] = val;
			st.update(co[i][0], co[i][1], -dp[i]);
			max = Math.max(max, dp[i]);
		}
		out.println(max);
	}
	
	private static int[][] stemp = new int[200005][];
	
	public static void mergesort(int[][] a, int s, int e)
	{
		if(e - s <= 1)return;
		int h = s+e>>1;
		mergesort(a, s, h);
		mergesort(a, h, e);
		int p = 0;
		int i= s, j = h;
		for(;i < h && j < e;)stemp[p++] = a[i][2] < a[j][2] ? a[i++] : a[j++];
		while(i < h)stemp[p++] = a[i++];
		while(j < e)stemp[p++] = a[j++];
		System.arraycopy(stemp, 0, a, s, e-s);
	}
	
	public static void mergesort0(int[][] a, int s, int e)
	{
		if(e - s <= 1)return;
		int h = s+e>>1;
		mergesort0(a, s, h);
		mergesort0(a, h, e);
		int p = 0;
		int i= s, j = h;
		for(;i < h && j < e;)stemp[p++] = a[i][0] < a[j][0] || a[i][0] == a[j][0] && a[i][1] < a[j][1] ? a[i++] : a[j++];
		while(i < h)stemp[p++] = a[i++];
		while(j < e)stemp[p++] = a[j++];
		System.arraycopy(stemp, 0, a, s, e-s);
	}
	
	public static class StaticRangeTreeRMQ2 {
		public int M, H, N;
		public SegmentTreeRMQL[] st;
		public int[][] maps;
		public long[][] vals;
		public int[] count;
		public long I = Long.MAX_VALUE;
		
		public StaticRangeTreeRMQ2(int[][] co, int n)
		{
			N = n;
			M = Integer.highestOneBit(Math.max(N-1, 1))<<2;
			H = M>>>1;
			
			mergesort0(co, 0, co.length);
//			Arrays.sort(co, new Comparator<int[]>() { // x asc
//				public int compare(int[] a, int[] b) {
//					if(a[0] != b[0])return a[0] - b[0];
//					return a[1] - b[1];
//				}
//			});
			maps = new int[M][];
			vals = new long[M][];
			st = new SegmentTreeRMQL[M];
			count = new int[M];
			for(int i = 0;i < co.length;i++){
				count[H+co[i][0]]++;
			}
			int off = 0;
			for(int i = 0;i < n;i++){
				maps[H+i] = new int[count[H+i]];
				for(int j = 0;j < count[H+i];j++,off++){
					maps[H+i][j] = co[off][1];
				}
				st[H+i] = new SegmentTreeRMQL(count[H+i]);
			}
			
			for(int i = H-1;i >= 1;i--){
				if(maps[2*i+1] == null){
					maps[i] = maps[2*i];
					count[i] = count[2*i];
				}else{
					count[i] = count[2*i] + count[2*i+1];
					maps[i] = new int[count[i]];
					int l = 0;
					for(int j = 0, k = 0;j < count[2*i] || k < count[2*i+1];l++){
						if(j == count[2*i]){
							maps[i][l] = maps[2*i+1][k++];
						}else if(k == count[2*i+1]){
							maps[i][l] = maps[2*i][j++];
						}else if(maps[2*i][j] < maps[2*i+1][k]){
							maps[i][l] = maps[2*i][j++];
						}else if(maps[2*i][j] > maps[2*i+1][k]){
							maps[i][l] = maps[2*i+1][k++];
						}else{
							maps[i][l] = maps[2*i][j++];
							k++;
						}
					}
					if(l != count[i]){ // uniq
						count[i] = l;
						maps[i] = Arrays.copyOf(maps[i], l);
					}
				}
				if(count[i] <= 25){ // 10% faster
					vals[i] = new long[count[i]];
					Arrays.fill(vals[i], Long.MAX_VALUE / 2);
				}else{
					st[i] = new SegmentTreeRMQL(count[i]);
				}
			}
		}
		
		public void update(int x, int y, long v)
		{
			outer:
			for(int pos = H+x;pos >= 1;pos>>>=1){
				if(st[pos] != null){
					int ind = Arrays.binarySearch(maps[pos], y);
					if(ind >= 0){
						st[pos].update(ind, v);
						continue;
					}
				}else{
					for(int i = 0;i < count[pos];i++){
						if(maps[pos][i] == y){
							vals[pos][i] = v;
							continue outer;
						}
					}
				}
				throw new RuntimeException(String.format("access to non-existing point : (%d,%d):%d", x, y, v));
			}
		}
		
		public long min(int xl, int xr, int yl, int yr) { return min(xl, xr, yl, yr, 0, H, 1); }
		
		public long min(int xl, int xr, int yl, int yr, int cl, int cr, int cur)
		{
			if(xl <= cl && cr <= xr){
				if(st[cur] != null){
					int indl = Arrays.binarySearch(maps[cur], yl);
					int indr = Arrays.binarySearch(maps[cur], yr);
					if(indl < 0)indl = -indl - 1;
					if(indr < 0)indr = -indr - 1;
					return st[cur].minx(indl, indr);
				}else{
					long min = I;
					for(int i = 0;i < count[cur] && maps[cur][i] < yr;i++){
						if(maps[cur][i] >= yl && vals[cur][i] < min) min = vals[cur][i];
					}
					return min;
				}
			}else{
				int mid = cl+cr>>>1;
				long ret = I;
				if(cl < xr && xl < mid)ret = Math.min(ret, min(xl, xr, yl, yr, cl, mid, 2*cur));
				if(mid < xr && xl < cr)ret = Math.min(ret, min(xl, xr, yl, yr, mid, cr, 2*cur+1));
				return ret;
			}
		}
	}
	
	public static class SegmentTreeRMQL {
		public int M, H, N;
		public long[] st;
		
		public SegmentTreeRMQL(int n)
		{
			N = n;
			M = Integer.highestOneBit(Math.max(N-1, 1))<<2;
			H = M>>>1;
			st = new long[M];
			Arrays.fill(st, 0, M, Long.MAX_VALUE/2);
		}
		
		public SegmentTreeRMQL(long[] a)
		{
			N = a.length;
			M = Integer.highestOneBit(Math.max(N-1, 1))<<2;
			H = M>>>1;
			st = new long[M];
			for(int i = 0;i < N;i++){
				st[H+i] = a[i];
			}
			Arrays.fill(st, H+N, M, Long.MAX_VALUE);
			for(int i = H-1;i >= 1;i--)propagate(i);
		}
		
		public void update(int pos, long x)
		{
			st[H+pos] = x;
			for(int i = (H+pos)>>>1;i >= 1;i >>>= 1)propagate(i);
		}
		
		private void propagate(int i)
		{
			st[i] = Math.min(st[2*i], st[2*i+1]);
		}
		
		public long minx(int l, int r){
			long min = Long.MAX_VALUE;
			if(l >= r)return min;
			while(l != 0){
				int f = l&-l;
				if(l+f > r)break;
				long v = st[(H+l)/f];
				if(v < min)min = v;
				l += f;
			}
			
			while(l < r){
				int f = r&-r;
				long v = st[(H+r)/f-1];
				if(v < min)min = v;
				r -= f;
			}
			return min;
		}
		
		public long min(int l, int r){ return l >= r ? 0 : min(l, r, 0, H, 1);}
		
		private long min(int l, int r, int cl, int cr, int cur)
		{
			if(l <= cl && cr <= r){
				return st[cur];
			}else{
				int mid = cl+cr>>>1;
				long ret = Long.MAX_VALUE;
				if(cl < r && l < mid){
					ret = Math.min(ret, min(l, r, cl, mid, 2*cur));
				}
				if(mid < r && l < cr){
					ret = Math.min(ret, min(l, r, mid, cr, 2*cur+1));
				}
				return ret;
			}
		}
		
		public int firstle(int l, long v) {
			int cur = H+l;
			while(true){
				if(st[cur] <= v){
					if(cur < H){
						cur = 2*cur;
					}else{
						return cur-H;
					}
				}else{
					cur++;
					if((cur&cur-1) == 0)return -1;
					if((cur&1)==0)cur>>>=1;
				}
			}
		}
		
		public int lastle(int l, long v) {
			int cur = H+l;
			while(true){
				if(st[cur] <= v){
					if(cur < H){
						cur = 2*cur+1;
					}else{
						return cur-H;
					}
				}else{
					if((cur&cur-1) == 0)return -1;
					cur--;
					if((cur&1)==1)cur>>>=1;
				}
			}
		}
	}

	
	void run() throws Exception
	{
		is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes());
		out = new PrintWriter(System.out);
		
		long s = System.currentTimeMillis();
		solve();
		out.flush();
		if(!INPUT.isEmpty())tr(System.currentTimeMillis()-s+"ms");
	}
	
	public static void main(String[] args) throws Exception { new D().run(); }
	
	private byte[] inbuf = new byte[1024];
	public int lenbuf = 0, ptrbuf = 0;
	
	private int readByte()
	{
		if(lenbuf == -1)throw new InputMismatchException();
		if(ptrbuf >= lenbuf){
			ptrbuf = 0;
			try { lenbuf = is.read(inbuf); } catch (IOException e) { throw new InputMismatchException(); }
			if(lenbuf <= 0)return -1;
		}
		return inbuf[ptrbuf++];
	}
	
	private boolean isSpaceChar(int c) { return !(c >= 33 && c <= 126); }
	private int skip() { int b; while((b = readByte()) != -1 && isSpaceChar(b)); return b; }
	
	private double nd() { return Double.parseDouble(ns()); }
	private char nc() { return (char)skip(); }
	
	private String ns()
	{
		int b = skip();
		StringBuilder sb = new StringBuilder();
		while(!(isSpaceChar(b))){ // when nextLine, (isSpaceChar(b) && b != ' ')
			sb.appendCodePoint(b);
			b = readByte();
		}
		return sb.toString();
	}
	
	private char[] ns(int n)
	{
		char[] buf = new char[n];
		int b = skip(), p = 0;
		while(p < n && !(isSpaceChar(b))){
			buf[p++] = (char)b;
			b = readByte();
		}
		return n == p ? buf : Arrays.copyOf(buf, p);
	}
	
	private char[][] nm(int n, int m)
	{
		char[][] map = new char[n][];
		for(int i = 0;i < n;i++)map[i] = ns(m);
		return map;
	}
	
	private int[] na(int n)
	{
		int[] a = new int[n];
		for(int i = 0;i < n;i++)a[i] = ni();
		return a;
	}
	
	private int ni()
	{
		int num = 0, b;
		boolean minus = false;
		while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
		if(b == '-'){
			minus = true;
			b = readByte();
		}
		
		while(true){
			if(b >= '0' && b <= '9'){
				num = num * 10 + (b - '0');
			}else{
				return minus ? -num : num;
			}
			b = readByte();
		}
	}
	
	private long nl()
	{
		long num = 0;
		int b;
		boolean minus = false;
		while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
		if(b == '-'){
			minus = true;
			b = readByte();
		}
		
		while(true){
			if(b >= '0' && b <= '9'){
				num = num * 10 + (b - '0');
			}else{
				return minus ? -num : num;
			}
			b = readByte();
		}
	}
	
	private static void tr(Object... o) { System.out.println(Arrays.deepToString(o)); }
}
                    


                        Solution in Python : 
                            
In  Python3 :




from collections import namedtuple
from bisect import bisect_left
import sys

Place = namedtuple('Place', 'lat, long, height, points')

chunkplaces={} # places get inserted into lists contained here, grouped by keys of their locations
chunkvals={} # holds values

giant = False
def getkey(place, off_lat=0, off_long=0):
    return ((place.lat // d_lat + off_lat) * 200011) + place.long // d_long + off_long # unique for n<=200000

def recordvalue(place, val):
    if val < 0:
        return # not worth going here; no need to track
    key = getkey(place)
    if key not in chunkplaces:
        chunkplaces[key] = []
        chunkvals[key] = []
    if giant:
        if len(chunkvals[key]) == 0:
            chunkvals[key].append(-val)
            chunkplaces[key].append(place)
        else:
            if val < -chunkvals[key][0]:
                return
            else:
                chunkvals[key][0] = -val
                chunkplaces[key][0] = place
    else:
        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]])

def getbestinchunk(place, key, best):
    # find best suitable match in chunk
    if key not in chunkvals:
        return 0
    for i, (cand, val) in enumerate(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; abort
            return 0
        if abs(place.lat - cand.lat) <= d_lat \
            and abs(place.long - cand.long) <= d_long :
            # and cand.height > place.height: # height is given, assuming they're unique
            # suitable, return it
            return -val
    # no suitable match
    return 0
   
def getbest(place):
    # find best match in this and neighboring chunks, then pick the best
    best = 0 # always have the option to stop here
    for i in [0,1,-1]:
        for j in [0,1,-1]:
            key = getkey(place, i, j)
            ret = getbestinchunk(place, key, best)
            if ret > best:
                best = ret
    return best
    
def calculatevalue(place):
    val = place.points + getbest(place)
    recordvalue(place, val)
    return val

if __name__ == "__main__":
    n, d_lat, d_long = input().strip().split(' ')
    n, d_lat, d_long = [int(n), int(d_lat), int(d_long)]
    places = []
    if d_lat == 200000:
        giant = True
    for a0 in range(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=lambda p: -p.height) # compute highest first
    best = 0
    for p in places:
        ret = calculatevalue(p)
        if ret > best:
            best = ret
    print(best)
                    


View More Similar Problems

Tree: Postorder Traversal

Complete the postorder function in the editor below. It received 1 parameter: a pointer to the root of a binary tree. It must print the values in the tree's postorder traversal as a single line of space-separated values. Input Format Our test code passes the root node of a binary tree to the postorder function. Constraints 1 <= Nodes in the tree <= 500 Output Format Print the

View Solution →

Tree: Inorder Traversal

In this challenge, you are required to implement inorder traversal of a tree. Complete the inorder function in your editor below, which has 1 parameter: a pointer to the root of a binary tree. It must print the values in the tree's inorder traversal as a single line of space-separated values. Input Format Our hidden tester code passes the root node of a binary tree to your $inOrder* func

View Solution →

Tree: Height of a Binary Tree

The height of a binary tree is the number of edges between the tree's root and its furthest leaf. For example, the following binary tree is of height : image Function Description Complete the getHeight or height function in the editor. It must return the height of a binary tree as an integer. getHeight or height has the following parameter(s): root: a reference to the root of a binary

View Solution →

Tree : Top View

Given a pointer to the root of a binary tree, print the top view of the binary tree. The tree as seen from the top the nodes, is called the top view of the tree. For example : 1 \ 2 \ 5 / \ 3 6 \ 4 Top View : 1 -> 2 -> 5 -> 6 Complete the function topView and print the resulting values on a single line separated by space.

View Solution →

Tree: Level Order Traversal

Given a pointer to the root of a binary tree, you need to print the level order traversal of this tree. In level-order traversal, nodes are visited level by level from left to right. Complete the function levelOrder and print the values in a single line separated by a space. For example: 1 \ 2 \ 5 / \ 3 6 \ 4 F

View Solution →

Binary Search Tree : Insertion

You are given a pointer to the root of a binary search tree and values to be inserted into the tree. Insert the values into their appropriate position in the binary search tree and return the root of the updated binary tree. You just have to complete the function. Input Format You are given a function, Node * insert (Node * root ,int data) { } Constraints No. of nodes in the tree <

View Solution →