90pts RE ON#9求助
查看原帖
90pts RE ON#9求助
675167
floaya楼主2024/5/3 19:19

个人感觉不应该是数组越界啊

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll read(){
    ll w=1,c,ret;
    while((c=getchar())> '9'||c< '0')
    w=(c=='-'?-1:1); ret=c-'0';
    while((c=getchar())>='0'&&c<='9')
    ret=ret*10+c-'0';
    return ret*w;
}
int const maxn=205;
int n,m,cnt;
struct node{
	int x,y,t,v;
	bool f;
}a[maxn];
bool p(node a,node b){
	if(a.y==b.y) return a.x<b.x;
	return a.y<b.y;
}
int mnv[maxn],mnt[maxn];
int exv[maxn][maxn],ext[maxn][maxn];
int f[40005];
int main(){
	n=read(),m=read();
	for(int i=1;i<=n;i++){
		a[i].x=read(),a[i].y=read(),a[i].t=read(),a[i].v=read();
		a[i].f=0;
	}
	sort(a+1,a+n+1,p);
	double k,l;
	
	for(int i=1;i<=n;i++){
		if(a[i].f) continue;
		if(a[i].x==0) k=0;
		else k=(1.0*a[i].y)/(1.0*a[i].x);
		a[i].f=1;
		mnv[++cnt]=a[i].v;
		mnt[cnt]=a[i].t;
		for(int j=i+1;j<=n;j++){
			if(a[j].f) continue;
			if(a[j].x==0) l=0;
			else l=(1.0*a[j].y)/(1.0*a[j].x);
			if(l==k){
				a[j].f=1;
				exv[cnt][0]++;
				exv[cnt][exv[cnt][0]]=a[j].v;
				ext[cnt][exv[cnt][0]]=a[j].t;
			}
		}
	}
	
	for(int i=1;i<=cnt;i++){
		for(int j=m,v=mnv[i],t=mnt[i];j>=mnt[i];j--){
			f[j]=max(f[j],f[j-t]+v);
			for(int k=1;k<=exv[i][0];k++){
				v+=exv[i][k];
				t+=ext[i][k];
				if(j>=t) f[j]=max(f[j],f[j-t]+v);
			}
		}
	}
	cout<<f[m];
	return 0;
}
/*

*/
2024/5/3 19:19
加载中...