普及培优班day4 A题贪心代码

[沈承樾1 (沈承樾)]

#include<bits/stdc++.h>
using namespace std;
const int N=209;
int n,h,t;
int p[N],d[N],c[N],s[N];
struct st{int num,id;}a[100009];
int cnt;
bool cmp(const st&a,const st&b){return a.num>b.num;}
int main(){
	cin>>n>>h>>t;
	h*=60;
	for(int i=1;i<=n;i++){
		scanf("%d%d%d",&p[i],&d[i],&c[i]);
		s[i]=s[i-1]+c[i-1];
	}
	for(int i=1;i<=n;i++){
		for(int j=1;p[i]-(j-1)*d[i]>0;j++) a[cnt++]=(st){p[i]-(j-1)*d[i],i};
	}
	sort(a,a+cnt,cmp);
	int ans=0;
	for(int i=1;i<=n;i++){
		for(int j=i;j<=n;j++){
			int dist=s[j]-s[i];
			int rem=h-dist;
			int tot=0,acnt=0;
			for(int k=0;k<cnt;k++){
				if(a[k].id>=i&&a[k].id<=j){
					tot+=a[k].num;
					acnt++;
					if((acnt+1)*t>rem) break;
				}
			}
			ans=max(ans,tot);
		}
	}
	cout<<ans<<endl;
	return 0;
}