Submission #1090

#	Time	Username	Problem	Language	Result	Execution time	Memory
1090		lmj960417	앱 (KOI13_app)	C++98	0 / 21	0 ms	40144 KiB

app

#include <stdio.h>
int n,m;
int ba[110],data[110];
int table[10000010];
int main()
{
	int i,a;
	int sum=0;

	freopen("input.txt","r",stdin);
	freopen("output.txt","w",stdout);

	scanf("%d %d",&n,&m);

	for(i=1;i<=n;i++)
	{
		scanf("%d ",&ba[i]);
	}
	for(i=1;i<=n;i++)
	{
		scanf("%d ",&data[i]);
		sum+=data[i];
	}

	if(n*m<=80000000)
	{
		for(i=1;i<=m;i++)
		{
			table[i]=sum;
		}
		table[0]=0;
		for(i=1;i<=n;i++)
		{
			for(a=m;a>=0;a--)
			{
				if(a+ba[i]<=m && table[a+ba[i]]>table[a]+data[i])
				{
					table[a+ba[i]]=table[a]+data[i];
				}
			}
		}
		printf("%d\n",table[m]);
	}
	else
	{
		table[0]=1;
		for(i=1;i<=n;i++)
		{
			for(a=sum;a>=0;a--)
			{
				if(table[a] && table[a+data[i]]<table[a]+ba[i])
				{
					table[a+data[i]]=table[a]+ba[i];
				}
			}
		}
		for(i=0;i<=sum;i++)
		{
			if(table[i]-1>=m)
			{
				printf("%d\n",i);
				break;
			}
		}
	}

	return 0;
}

• Subtask 1: 0 / 3.15
• Subtask 2: 0 / 3.15
• Subtask 3: 0 / 3.15
• Subtask 4: 0 / 3.15
• Subtask 5: 0 / 3.15
• Subtask 6: 0 / 3.15
• Subtask 7: 0 / 2.1