https://www.luogu.com.cn/record/201506289

#include<algorithm>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<queue>
#include<vector>
#include<stack>
#include<map>
#include<set>
#include<ctime>
#include<cstdlib>
//#include<cmath>
using namespace std;
const int constant=50000005;
int dp[constant],n,c[constant],p[constant],t[constant],ts1,te2,ts2,te1,T;
int main(){
	scanf("%d:%d",&ts1,&te1);
	scanf("%d:%d",&ts2,&te2);
	scanf("%d",&n);
	T=(ts2-ts1)*60+(te2-te1);
	for(int i=1;i<=n;i++){
		scanf("%d%d%d",&t[i],&c[i],&p[i]);
	}
	for(int i=1;i<=n;i++){
		if(p[i]==0){
			for(int j=t[i];j<=T;j++){
				dp[j]=max(dp[j],dp[j-t[i]]+c[i]);
			}
		}
		else if(p[i]==1){
			for(int j=T;j>=t[i];j--){
	  			dp[j]=max(dp[j],dp[j-t[i]]+c[i]);
			}
		}
		else{
			for(int k=1;k<=p[i];k++){
				for(int j=T;j>=t[i]*k;j--){
					dp[j]=max(dp[j],dp[j-t[i]*k]+c[i]*k);
				}
			}
		}
	}
	printf("%d",dp[T]);
	return 0;
}