|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 |
#include <iostream> #include <vector> #include <algorithm> using namespace std; struct order{ int start; int dest; int pss; int prft; }; vector<order> vb; int cap,b,num_order; int result; int passenger_cap[10]; int solve(int position_order,int max) { if(result<max) result=max; int f; while(position_order<=(num_order-1)) { f=0; for(int i=vb[position_order].start;i<vb[position_order].dest;i++) { passenger_cap[i]+=vb[position_order].pss; if(passenger_cap[i]>cap) { f=1; //break; } } if(!f) { solve(position_order+1,max+vb[position_order].prft); } for(int i=vb[position_order].start;i<vb[position_order].dest;i++) passenger_cap[i]-=vb[position_order].pss; position_order++; } return 0; } int main() { int x,y,z; order o; while(cin>>cap) { cin>>b>>num_order; if(cap==0 && b==0 && num_order==0) break; vb.clear(); for(int i=0;i<num_order;i++) { cin>>x>>y>>z; o.start=x; o.dest=y; o.pss=z; o.prft=(y-x)*z; vb.push_back(o); } for(int i=0;i<10;i++) passenger_cap[i]=0; result=0; solve(0,0); cout<<result<<"\n"; } return 0; } |