oj.uz

Submission #1091

# Submission time Handle Problem Language Result Execution time Memory
1091 2013-06-25T05:39:05 Z lmj960417 앱 (KOI13_app) C++
0 / 21
 204 ms 40152 KB 
#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.0 / 3.15

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 40152 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 3.15

# Verdict Execution time Memory Grader output
1 Correct 0 ms 40152 KB Output is correct
2 Incorrect 0 ms 40152 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0.0 / 3.15

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 40152 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 3.15

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 40152 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 3.15

# Verdict Execution time Memory Grader output
1 Correct 0 ms 40152 KB Output is correct
2 Correct 0 ms 40152 KB Output is correct
3 Correct 0 ms 40152 KB Output is correct
4 Correct 0 ms 40152 KB Output is correct
5 Incorrect 120 ms 40152 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #6
0.0 / 3.15

# Verdict Execution time Memory Grader output
1 Correct 0 ms 40152 KB Output is correct
2 Incorrect 184 ms 40152 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0.0 / 2.1

# Verdict Execution time Memory Grader output
1 Incorrect 204 ms 40152 KB Output isn't correct
2 Halted 0 ms 0 KB -