1961527_ac_0ms_28k.c

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

# include <stdio.h>
# include <string.h>
# include <stdlib.h>
# define MAX 45

int mark;
__int64 C;
__int64 max = -1;
__int64 a[MAX], b[MAX];

void search(__int64 c, int n, __int64 m)
{
	int i;

	for(i = n-1; i >= 0; i--)
	{
		if(max == C)
			return ;
		if(c >= b[i])
		{
			search(c-b[i],0,m+b[i]);
			return ;
		}
		if(a[i] > c)
			continue;
		else
		{
			search(c-a[i],i,m+a[i]);
		}
	}
	if(m > max)
		max = m;
}

int main()

{
	int i, j, N;
	__int64 tmp;

	scanf("%d%I64d",&N,&C);
	j = 0;
	tmp = 0;
	for(i = 0; i < N; i++)
	{
		scanf("%I64d",&a[i]);
		if(a[i] > C)
		{
			i--;
			N--;
		}
		else
		{
			tmp += a[i];
			b[i] = tmp;
		}
	}
	search(C,i,0);
	printf("%I64d\n",max);
	return 1;
}