比赛 201712练习 评测结果 AAAAAAAAAA
题目名称 硬币问题 最终得分 100
用户昵称 サイタマ 运行时间 0.021 s
代码语言 C++ 内存使用 0.44 MiB
提交时间 2017-12-22 19:44:32
显示代码纯文本
#include<cstdio>
using namespace std;
int read(int &x)
{
	bool flags;char ch;
	flags=false;
	while(ch=getchar(),ch<48 || 57<ch)if(ch=='-')flags=true;
	x=ch^'0';
	while(ch=getchar(),48<=ch && ch<=57)x=x*10+(ch^'0');
	if(flags)return -x;
	else return x;
}
int n,s,v[100001],i,j,a[100001],wa[100001],b[100001],wb[100001],s1;
int lyh()
{
	freopen("kouka.in","r",stdin);
	freopen("kouka.out","w",stdout);
	read(n);
	read(s);
	s1=s;
	for(i=1;i<=n;i++)read(v[i]);
	for(i=1;i<=100000;i++)a[i]=-1000000,b[i]=1000000;
	for(i=1;i<=s;i++)
		for(j=1;j<=n;j++)
		{
			if(i<v[j])continue;
			if(a[i]<a[i-v[j]]+1)
			{
				a[i]=a[i-v[j]]+1;
				wa[i]=j;
			}
			if(b[i]>b[i-v[j]]+1)
			{
				b[i]=b[i-v[j]]+1;
				wb[i]=j;
			}
		}
	printf("%d %d\n",b[s],a[s]);
	while(s1>0)
	{
		printf("%d ",wb[s1]);
		s1-=v[wb[s1]];
	}
	printf("\n");
	while(s>0)
	{
		printf("%d ",wa[s]);
		s-=v[wa[s]];
	}
	return 0;
}
int Main=lyh();
int main(){;}