P1833求调
  • 板块灌水区
  • 楼主IAKpoki
  • 当前回复0
  • 已保存回复0
  • 发布时间2025/2/8 09:17
  • 上次更新2025/2/8 11:31:20
查看原帖
P1833求调
1199889
IAKpoki楼主2025/2/8 09:17
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int t1h,t1m,t2h,t2m;
int v[100010];
int w[100010];
int len = 0; 
int dp[N];
int main(){
	int n,m;
	scanf("%d:%d %d:%d %d",&t1h,&t1m,&t2h,&t2m,&n);
	m=(t2h-t1h)*60+t2m-t1m;
	for(int i = 1; i <= n ; i++){
		int wi,vi,ci;
		cin >> wi >> vi >> ci;
		for(int j = 1 ; j <= ci ; j<<=1){
			w[++len] = wi * j;
			v[len] = vi * j;
			ci -= j;
		}
		if(ci != 0){
			w[++len] = wi * ci;
			v[len] = vi * ci;
		}
	}
	for(int i = 1;i <= len ; i++){
		for(int j = m ; j >= v[i] ; j--){
			dp[j] = max(dp[j],dp[j - v[i]] + w[i]);
		}
	}
	cout << dp[m];
	return 0;
}
2025/2/8 09:17
加载中...