Photolog
2010-10-12: Through the Looking-Glass
2010-10-10: My radio speaks is binary!
2010-09-16: Gigaminx: (present for my birthday)
2010-09-05: Trini on bike
2010-08-28: Valporquero
2010-08-22: My new bike!
2010-08-13: Mario and Ana's wedding
2010-08-07: Canyoning in Guara
2010-08-05: Trini and Mari in Marbella
2010-08-03: Trini and Chelo in Tabarca
Back to list of problems
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);
}