Fotolog

A través del espejo
2010-10-12: A través del espejo
¡La radio habla en binario!
2010-10-10: ¡La radio habla en binario!
Gigaminx (regalo por mi cumple)
2010-09-16: Gigaminx (regalo por mi cumple)
Trini en bici
2010-09-05: Trini en bici
Valporquero
2010-08-28: Valporquero
Mi bici nueva
2010-08-22: Mi bici nueva
Boda de Mario y Ana
2010-08-13: Boda de Mario y Ana
De cañones en Guara
2010-08-07: De cañones en Guara
Trini y Mari en Marbella
2010-08-05: Trini y Mari en Marbella
Trini y Chelo en Tabarca
2010-08-03: Trini y Chelo en Tabarca
Valid XHTML 1.1
Acceder
Volver a la lista de problemas

Transportation

301.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

int capacity, stations, orders;
int start[22], end[22], pass[22];

int pas_stat[7];

void calculate(void)
{
	int max_earning=0;
	int i,j,k;

	for(i=0; i< (1<<orders); i++) {
		int ok=1;
		int earning=0;
		for(j=0; j<stations; j++) {
			pas_stat[j]=0;
		}
		for(j=0; j<orders; j++) {
			if (i & (1<<j)) {
				for(k=start[j]; k<end[j]; k++) {
					pas_stat[k]+=pass[j];
					if (pas_stat[k]>capacity) {
						ok=0;
					}
				}
			}
		}
		for(k=0; k<stations; k++) {
			earning += pas_stat[k];
		}
		if (ok && (earning>max_earning)) {
			max_earning=earning;
		}
	}
	printf("%d\n", max_earning);
}

int main(int argc, char *argv[])
{
	char buf[1024];
	int i;

	while(fgets(buf, 1024, stdin)) {
		if (sscanf(buf, "%d %d %d", &capacity, &stations, &orders)!=3) {
			exit(1);
		}
		if ((capacity==0) && (stations==0) && (orders==0)) {
			exit(0);
		}
		for(i=0; i<orders; i++) {
			if (!fgets(buf, 1024, stdin)) {
				exit(2);
			}
			if (sscanf(buf, "%d %d %d", &start[i], &end[i], &pass[i])!=3) {
				exit(3);
			}
		}
		calculate();
	}
	exit(0);
}