rt，混合背包，多重背包部分二进制分拆

#include<bits/stdc++.h>
using namespace std;
int h1,m1,h2,m2,ft,n;
char hm1,hm2;
int f[114514],t[114514],c[114514],p[114514],cnt;
int main(){
	scanf("%d%c%d%d%c%d%d",&h1,&hm1,&m1,&h2,&hm2,&m2,&n);
	ft=h2*60+m2-m1-h1*60;
	for(int i=1;i<=n;i++){
		cin>>t[i]>>c[i]>>p[i];
	}
	for(int i=1;i<=n;i++){
		if(p[i]==1){
			for(int j=ft;j>=t[i];j--){
				f[j]=max(f[j],f[j-t[i]]+c[i]);
			}
		}
		if(p[i]==0){
			for(int j=t[i];j<=ft;j++){
				f[j]=max(f[j],f[j-t[i]]+c[i]);
			}
		}
		else {
			for(int k=1;k<=p[i];p[i]-=k,k*=2){
				for(int j=ft;j>=t[i]*k;j--){
					f[j]=max(f[j],f[j-t[i]*k]+c[i]*k);
				}
			}
			if(p[i]>0){
				for(int j=ft;j>=t[i]*p[i];j--){
					f[j]=max(f[j],f[j-t[i]*p[i]]+c[i]*p[i]);
				}
			}
		}
	}
	cout<<f[ft];
	return 0;
}