有二进制优化

#include<bits/stdc++.h>
using namespace std;
int c,k;
int d[100010];
int w[100010];
int p[100010];
int s[100010];
int b,b1,e,e1,n;
int main()
{
    scanf("%d:%d",&b,&b1);
    scanf("%d:%d",&e,&e1);
    n=(e*60+e1)-(b*60+b1);
	cin>>c;
	for(int i=1;i<=c;i++)
	{
		int wi,pi,si;
		cin>>wi>>pi>>si;
		if(si>0)
		{
			int t=1;
			while(t<=si)
			{
				k++;
				w[k]=t*wi;
				p[k]=t*pi;
				si=si-t;
				t=t*2;
				s[k]=1;
			}
			if(si>0)
			{
				k++;
				w[k]=si*wi;
				p[k]=si*pi;
				s[k]=1;
			}
		}
		else
		{
			k++;
			w[k]=wi;
			p[k]=pi;
			s[k]=si;
		}
	}
	for(int i=1;i<=k;i++)
	{
		if(s[k]==1)
		{
			for(int j=n;j>=w[i];j--)
			{
				d[j]=max(d[j],d[j-w[i]]+p[i]);
			}
		}
		else if(s[k]==0)
		{
			for(int j=w[i];j<=n;j++)
			{
				d[j]=max(d[j],d[j-w[i]]+p[i]);
			}
		}
	}
	cout<<d[n];
}

qwq