2332993_ac_780ms_5012k.cc

北大大牛代码 1240道题的原代码 超级权威

#include <algorithm>

using namespace std;

int l, b, n, ans;
struct node
{
	int st, ed;
	int c, f;
}Edge[10001];
struct Node
{
	int num;
	int inf[1101][2];
}pot[1001];

bool cmp(struct node a,struct node b)
{
	if(a.st == b.st)
		return a.ed < b.ed;
	else
		return a.st < b.st;
}

int main()
{
	int i, j, k;
	int x, w, tc, tf;

	scanf("%d%d%d",&l,&n,&b);
	for(i = 0; i < n; i++)
	{
		scanf("%d%d%d%d",&x,&w,&Edge[i].f,&Edge[i].c);
		Edge[i].st = x;Edge[i].ed = x+w;
	}
	for(i = 0; i <= l; i++)
		pot[i].num = 0;
	pot[0].num = 1;
	pot[0].inf[1][0] = pot[0].inf[1][1] = 0;
	sort(Edge,Edge+n,cmp);
	for(i = 0; i < n; i++)
	{
		for(j = 1; j <= pot[Edge[i].st].num; j++)
		{
			tc = pot[Edge[i].st].inf[j][0]+Edge[i].c;
			tf = pot[Edge[i].st].inf[j][1]+Edge[i].f;
			if(tc<=b)
			{
				for(k = 1; k <= pot[Edge[i].ed].num; k++)
					if(tc>=pot[Edge[i].ed].inf[k][0]&&tf<=pot[Edge[i].ed].inf[k][1])
						goto con;
				pot[Edge[i].ed].inf[++pot[Edge[i].ed].num][0] = tc;
				pot[Edge[i].ed].inf[pot[Edge[i].ed].num][1] = tf;
			}
con:;
		}
	}
	ans = -1;
	for(i = 1; i <= pot[l].num; i++)
	{
		if(pot[l].inf[i][1] > ans)
			ans = pot[l].inf[i][1];
	}
	printf("%d\n",ans);
	return 1;
}