UVa 10440 - Ferry Loading II

// UVa 10440 - Ferry Loading II

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;

#define MaxM 2001

typedef unsigned long long ll;

ll a[MaxM];
ll T[MaxM];

int main() {
	int cases;
	for (scanf("%d", &cases); cases; cases--) {
		int n, t, m;
		scanf("%d%d%d", &n, &t, &m);

		memset(T, 255, sizeof(T));
		T[0] = 0;
		for (int i = 1; i <= m; i++) {
			scanf("%llu", &a[i]);
			for (int j = max(0, i - n); j < i; j++) {
				if (T[i] > max(a[i], T[j]) + 2 * t)
					T[i] = max(a[i], T[j]) + 2 * t;
			}
		}

		ll time = T[m] - 2 * t;
		int trips = 0;
		int i = m;
		while (i > 0) {
			trips++;
			int j;
			for (j = i; j > 0 && (j > i - n || a[j] >= time); j--)
				;
			i = j;
			time -= 2 * t;
		}

		printf("%llu %d\n", T[m] - t, trips);

	}

	return 0;
}