UVa 607 - Scheduling Lectures

// UVa 607 - Scheduling Lectures
#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;

int L, C;

int D(int lect) {
	int t = L - lect;
	if (t == 0)
		return 0;
	if (t <= 10)
		return -C;
	else
		return (t - 10) * (t - 10);
}

int main() {
	int cases = 0;
	int n;
	cin >> n;
	while (n) {
		cases++;
		cin >> L >> C;
		int lectures = 1;
		int current_lecture = 0;
		int topic[1001];
		for (int i = 1; i <= n; i++) {
			cin >> topic[i];
			if (topic[i] + current_lecture <= L)
				current_lecture += topic[i];
			else {
				current_lecture = topic[i];
				lectures++;
			}
		}

		if (cases > 1)
			printf("\n");
		printf("Case %d:\n", cases);
		printf("Minimum number of lectures: %d\n", lectures);

		signed long long int T[2][1001];
		memset(T, 127, sizeof(T));
		signed long long int oo = T[0][0];
		// base cases
		current_lecture = 0;
		topic[0] = 0;
		for (int i = 0; i <= n; i++) {
			current_lecture += topic[i];
			if (current_lecture > L)
				break;
			T[1][i] = D(current_lecture);
		}
		// calculate total disatisfaction index
		for (int ll = 2; ll <= lectures; ll++) {
			int l = ll % 2;
			T[l][0] = D(0) * ll;
			for (int i = ll; i <= n; i++) {
				T[l][i] = oo;
				current_lecture = 0;
				for (int j = i; j >= ll; j--) {
					current_lecture += topic[j];
					if (current_lecture > L)
						break;
					else {
						if (T[(l + 1) % 2][j - 1] != oo && T[l][i] > T[(l + 1) % 2][j - 1] + D(current_lecture))
							T[l][i] = T[(l + 1) % 2][j - 1] + D(current_lecture);
					}
				}
			}
		}
		printf("Total dissatisfaction index: %lld\n", T[lectures % 2][n]);

		cin >> n;
	}

	return 0;
}