Rent your Airplane and make Money

airplane.cpp

//http://coj.uci.cu/24h/problem.xhtml?abb=1005
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>

using namespace std;

struct plane {
    int st, end, prize;
} u[10005];

bool operator<(plane a, plane b) {
    return a.st < b.st;
}

int n;
int memo[10005];

int next(int imin, int imax, int i) {
    if(i == n-1) return n;
    if(imax < imin)
        return n;
    else {
        int imid = (imin + imax)/2;
        if(u[imid].st < u[i].end) {
            //busca a la derecha
            return next(imid+1,imax,i);
        } else {
            // case u[imid].st >= u[i].end
            if(u[imid-1].st < u[i].end) {
                // si uno antes interlapa
                return imid;
            }
            // si no, entonces buscamos a la izquierda
            else {
                return next(imin,imid-1,i);
            }
        }
    }
}

int dp(int i) {
    if(i == n) return 0;
    if(memo[i] != -1) return memo[i];
    return memo[i] = max(dp(i+1), u[i].prize+dp(next(i,n-1,i)));
}

int main() {
    int T;
    scanf("%d", &T);

    int st, d, price;

    while(T--) {
        scanf("%d", &n);
        memset(memo,(-1),sizeof(memo));
        for(int i = 0; i < n; i++) {
            scanf("%d %d %d", &st, &d, &price);
            u[i].st = st;
            u[i].end = st+d;
            u[i].prize = price;
        }
        sort(u,u+n);
        printf("%d\n",dp(0));
    }

    return 0;
}