代码

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;

int f[40005],n,m,w[40005],v[40005],tot=0;

bool fl[40005];

int main()
{
	int t1,t2,t3,t4;
	scanf("%d:%d%d:%d%d",&t1,&t2,&t3,&t4,&m);
	n=(t3*60+t4)-(t1*60+t2);
	for(int i=1;i<=m;i++)
	{
		int w1,v1,p;
		cin>>w1>>v1>>p;
		if(p)
		{
			for(int k=1;k<=p;k<<=1)
			{
				v[++tot]=k*v1;
				w[tot]=k*w1;
				p-=k;
				fl[tot]=1;
			}
			if(p)
			{
				v[++tot]=p*v1;
				w[tot]=p*w1;
				fl[tot]=1;
			}
		}
		else
		{
			v[++tot]=v1;
			w[tot]=w1;
			fl[tot]=0;	
		}
	}
	for(int i=1;i<=tot;i++)
	{
		if(fl[i])
		{
			for(int j=n;j>=w[i];j--)
			{
				f[j]=max(f[j],f[j-w[i]]+v[i]);
			}
		}
		else
		{
			for(int j=w[i];j<=n;j++)
			{
				f[j]=max(f[j],f[j-w[i]]+v[i]);
			}
		}
	}
	cout<<f[n];
	return 0;
}