Say that we've built some the first few sections of our roller coaster, and say that these first few sections have a total length of 10 (stretching from position 0 to position 10). Suppose that they cost us $15 and gave us a fun of 20. If there was a different way to build up to position 10 which cost $15 and which gives a fun of 19, would we want to use it, ever? No, because we could just substitute the more fun components with a fun of 20 for the less fun ones, and then we could finish the roller coaster exactly the same as we were going to.
The key point here is that if we've built up to position 10, it doesn't matter how we got there: the only things that matter are how much money we spent and how fun it was. This allows us to use the technique of Dynamic Programming.
We make a table "FUN" of size L+1 by B+1 (where L is the total length of the roller coaster and B is the total budget). The entry at FUN[i][j] will be the maximum amount to fun we can have gotten so far after having built up to position i and spent j dollars. We start by initializing the table to minus infinity and then FUN[0][0] to 0. This indicates that we don't know yet how to have any fun, except that we know that we can have no fun and get no where by building nothing.
We now walk through the table FUN[i][j] from the left (at position i=0) to the right (at position i=L). For each position i, we loop through all of the different roller coaster components k that can be built starting at position i. The width of component k is Wk and the cost is Ck and the fun Fk. For each amount of money j that we could have already spent, if we can build component k within our budget (i.e. if j+Ck <= B), then we see if doing so yields a more fun partial coaster at position i+Wk and cost j+Ck then we already have in the table at FUN[i+Wk][j+Ck]. That is, we check to see if FUN[i][j] + Fk > FUN[i+Wk][j+Ck]. If it is, then we update FUN[i+Wk][j+Ck] with the higher value. Since we only ever update a value to the right of where we are now, and since we walk through the table from left to right, we will have the best (correct) value by the time we walk to a table entry.
After we're done with this, we just need to read off the most fun coaster from among the entries at FUN[L][j] for all costs j with 0 <= j <= B. If these values are all minus infinity, then we know that we can't actually get from the start by building components, and thus we can't actually build the coaster, and we output -1.
#include <stdlib.h>
#include <stdio.h>
const int MAXL = 1001 + 100;
const int MAXN = 20000 + 200;
const int MAXB = 1001 + 100;
int len, n, budget;
struct component {
int start;
int width;
int fun;
int cost;
} coaster[MAXN];
int comp_cmp(const void *p1, const void *p2){
return((((component*)p1)->start) - (((component*)p2)->start));
}
int best[MAXL][MAXB];
int main(){
FILE *fin = fopen("coaster.in", "r");
fscanf(fin, "%d %d %d", &len, &n, &budget);
for(int i = 0; i < n; ++i){
fscanf(fin, "%d %d %d %d", &coaster[i].start, &coaster[i].width,
&coaster[i].fun, &coaster[i].cost);
}
fclose(fin);
//fprintf(stderr, "line %d\n", __LINE__);
for(int i = 0; i <= len; ++i){
for(int j = 0; j <= budget; ++j){
best[i][j] = -1;
}
}
for(int i = 0; i <= budget; ++i){
best[0][i] = 0;
}
qsort(coaster, n, sizeof(component), comp_cmp);
for(int i = 0; i < n; ++i){
for(int c = 0; c <= budget-1; ++c){
if(best[coaster[i].start][c] == -1) continue;
best[coaster[i].start + coaster[i].width][c + coaster[i].cost] >?= best[coaster[i].start][c] + coaster[i].fun;
}
}
FILE *fout = fopen("coaster.out", "w");
fprintf(fout, "%d\n", best[len][budget]);
fclose(fout);
return(0);
}