RE惨案 求助
  • 板块P1833 樱花
  • 楼主JURUOzhao
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/10/5 12:42
  • 上次更新2024/10/5 12:49:48
查看原帖
RE惨案 求助
969039
JURUOzhao楼主2024/10/5 12:42
#include<bits/stdc++.h>
using namespace std;
long long c[5005000],p[5005000],t[5000050],n,tt,t11,t12,t21,t22;
long long cnt[5000500],dp[5001000];
char cc;
struct nd{
	long long w,tim;
};
vector<nd>v[500050];
int main(){
	cin>>t11>>cc>>t12>>t21>>cc>>t22;
	cin>>n;
	tt=(t21-t11+24)%24*60+t22-t12;
	for(long long i=1;i<=n;i++){
		cin>>t[i]>>c[i]>>p[i];
	}
	//17=1+2+4+8+2 8<=10 8<=17
	//17=1+2+4+8+16+1 16<=2
	for(long long i=1;i<=n;i++){
		if(p[i]){
		long long sum=0;
		long long base=1;
		while(base<=p[i]){
			v[i].push_back({base*c[i],base*t[i]});
			base<<=1;
			sum++;
			p[i]-=base;
		}
		v[i].push_back({p[i]*c[i],p[i]*t[i]});
		cnt[i]=sum;
		}
	}
	dp[0]=0;
	for(long long i=1;i<=n;i++){
		if(p[i]){
			for(auto x:v[i]){
				for(long long j=tt;j>=x.tim;j--){
				dp[j]=max(dp[j],dp[j-x.tim]+x.w);
				}
			}
			
		}
		else{
			for(long long j=t[i];j<=tt;j++){
			dp[j]=max(dp[j],dp[j-t[i]]+c[i]);
			}
		}
	}
	cout<<dp[tt];
	return 0;
}
2024/10/5 12:42
加载中...