RENT.cpp

#include <iostream>
using namespace std;

const int MAX = 10005;

int N;
int Start[MAX], Finish[MAX], Price[MAX];
long long Memo[MAX];	
// Memo[i] là số tiền lớn nhất khi chỉ chọn các đơn hàng từ 1 đến i

void QuickSort(int left, int right)
{
	int l = left, r = right;
	int pivot = Finish[(l + r) / 2];

	while(l <= r)
	{
		while(Finish[l] < pivot) l++;
		while(Finish[r] > pivot) r--;

		if(l <= r)
		{
			int temp1 = Finish[l];	int temp2 = Start[l];	int temp3 = Price[l];
			Finish[l] = Finish[r];	Start[l] = Start[r];	Price[l] = Price[r];
			Finish[r] = temp1;		Start[r] = temp2;		Price[r] = temp3;	
			l++;
			r--;
		}	
	}

	if(l < right) QuickSort(l, right);
	if(left < r) QuickSort(left, r);
}

// Tìm số k lớn nhất thoả mãn Finish[k] < Start[i]
// Nếu không tìm thấy thì trả về -1
int BinarySearch(int i)
{
	int left = 1, right = i;
	int k;

	while(left < right - 1)
	{
		k = (left + right) / 2;

		if(Finish[k] < Start[i]) left = k;
		else right = k - 1;
	}

	if(Finish[right] < Start[i]) return right;
	if(Finish[left] < Start[i]) return left;
	return -1;
}

int main(int argc, char** argv)
{
	int T, test_case;
	//freopen("input.txt", "r", stdin);
	ios::sync_with_stdio(false);

	cin >> T;
	for(test_case = 0; test_case  < T; test_case++)
	{
		// Nhập đầu vào
		int d;
		cin >> N;
		for(int i = 1; i <= N; i++)
		{
			cin >> Start[i] >> d >> Price[i];
			Finish[i] = Start[i] + d;
		}

		// Sắp xếp các đơn hàng theo chiều tăng của thời gian kết thúc
		QuickSort(1, N);

		// Trường hợp cơ sở
		for(int i = 1; i <= N; i++)
			Memo[i] = (long long)Price[i];

		for(int i = 2; i <= N; i++)
		{
			// Không chọn đơn hàng thứ i
			if(Memo[i-1] > Memo[i]) Memo[i] = Memo[i-1];

			// Chọn đơn hàng thứ i
			// Tìm số k lớn nhất sao cho Finish[k] < Start[i]
			int k = BinarySearch(i);
			long long temp = (long long)Price[i] + (long long)Memo[k];
			if(k > -1 && temp > Memo[i]) Memo[i] = temp;
		}

		// Print the answer to standard output(screen).
		cout << Memo[N] << endl;
	}
	return 0;//Your program should return 0 on normal termination.
}