80pts求助 QAQ
查看原帖
80pts求助 QAQ
370618
陈霖瑄0226楼主2022/5/19 22:33
#include<bits/stdc++.h>
using namespace std;

#define int long long

void read(int* a)
{
	char c=getchar();
	int x=0,f=1;
	while(c<'0'||c>'9')
	{
		if(c=='-') f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9')
	{
		x=x*10+c-'0';
		c=getchar();
	}
	*a=x*f;
}

void Read(){}
template<typename TYPE,typename... TYPES>
void Read(TYPE& x,TYPES&... y)
{
    read(&x);
    Read(y...);
}

void READ(int* a,int* b)
{
	for(int i=0;i<=b-a;i++)
	{
		read(a+i);
	}
}

void write(const int* c)
{
	int a=*c,i=0,b[101];
	if(a<0) putchar('-'),a=-a;
	while(a)
	{
		b[++i]=a%10;
		a/=10;
	}
	while(i)
	{
		putchar(b[i]+'0');
		i--;
	}
	putchar(' ');
}

void Write(){}
template<typename TYPE,typename... TYPES>
void Write(TYPE& x,TYPES&... y)
{
    write(&x);
    Write(y...);
}

void WRITE(int* a,int* b)
{
	for(int i=0;i<=b-a;i++)
	{
		write(a+i);
	}
}

int n,t,dp[10001];

void A_01 (int v,int w)
{
	for(int i=t;i>=w;i--)
	{
		if(i>=w)dp[i]=max(dp[i-w]+v,dp[i]);
	}
}

void C (int v,int w)
{
	for(int i=w;i<=t;i++)
	{
		if(i>=w)dp[i]=max(dp[i-w]+v,dp[i]);
	}
}

int v[10001],w[10001],m[10001];

void B (int i)
{
	int a=1;
	if(w[i]*i>=t)
	{
		C(v[i],w[i]);
		return;
	}
	while(m[i]>=a)
	{
		A_01(v[i]*a,w[i]*a);
		m[i]-=a;
		a*=2;
	}
	if(m[i]>0)a=m[i],A_01(v[i]*a,w[i]*a);;
}

int h1,h2,m1,m2;

#undef int

int main()
{
	Read(h1,m1,h2,m2,n);
	t=(h2-h1)*60+(m2-m1);
	for(int i=1;i<=n;i++) 
	{
		Read(w[i],v[i],m[i]);
		if(m[i]==0) m[i]=t*5;
		B(i);
	}
	cout<<dp[t];
	return 0;
}
2022/5/19 22:33
加载中...