oj.uz

Submission #222450

# Submission time Handle Problem Language Result Execution time Memory
222450 2020-04-13T07:37:51 Z compilers 앱 (KOI13_app) C++14
21 / 21
 10 ms 4224 KB 
#include	<iostream>

using namespace	std;

#define	MAX_SIZE	(100+1)
#define	MAX_COST	(10000+1)

int	N,M,free_memory_table[MAX_SIZE][MAX_COST];
int	m[MAX_SIZE],c[MAX_SIZE];

int	main(void)
{
	cin>>N>>M;
	
	for(int app=0;app<=N;app++)
	{
		fill(&free_memory_table[app][0],&free_memory_table[app][MAX_COST],-1);
	}
	
	free_memory_table[0][0] = 0;
	
	for(int app=1;app<=N;app++)
	{
		cin>>m[app];
	}
	
	for(int app=1;app<=N;app++)
	{
		cin>>c[app];
	}
	
	for(int app=1;app<=N;app++)
	{
		int&	current_app_memory = m[app];
		int&	current_app_cost = c[app];
		int		prev_app;
		
		prev_app = app-1;
		
		for(int cost=0;cost<MAX_COST;cost++)
		{
			if( free_memory_table[prev_app][cost] != -1 )
			{
				free_memory_table[app][cost] =
					max(free_memory_table[prev_app][cost],free_memory_table[app][cost]);
				
				free_memory_table[app][cost+current_app_cost] =
					max(free_memory_table[app][cost+current_app_cost],
						free_memory_table[prev_app][cost]+current_app_memory);
			}
		}
	}
	
	int		min_cost;
	int&	last_app = N;
	
	min_cost = MAX_COST;
		
	for(int cost=0;cost<MAX_COST;cost++)
	{
		if( free_memory_table[last_app][cost] >= M )
		{
			min_cost = min(min_cost,cost);
		}
	}
	
	cout<<min_cost<<'\n';
	
	return	0;
}

Subtask #1
3.15 / 3.15

# Verdict Execution time Memory Grader output
1 Correct 5 ms 768 KB Output is correct
2 Correct 6 ms 1152 KB Output is correct
3 Correct 5 ms 1152 KB Output is correct
4 Correct 5 ms 1152 KB Output is correct
5 Correct 5 ms 512 KB Output is correct
6 Correct 5 ms 1152 KB Output is correct

Subtask #2
3.15 / 3.15

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 1024 KB Output is correct
3 Correct 5 ms 640 KB Output is correct
4 Correct 5 ms 768 KB Output is correct
5 Correct 5 ms 512 KB Output is correct

Subtask #3
3.15 / 3.15

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1920 KB Output is correct
2 Correct 6 ms 1280 KB Output is correct
3 Correct 6 ms 2176 KB Output is correct
4 Correct 6 ms 2048 KB Output is correct
5 Correct 6 ms 2176 KB Output is correct
6 Correct 6 ms 2048 KB Output is correct

Subtask #4
3.15 / 3.15

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1152 KB Output is correct
2 Correct 6 ms 2048 KB Output is correct
3 Correct 6 ms 1920 KB Output is correct
4 Correct 6 ms 2176 KB Output is correct
5 Correct 6 ms 1920 KB Output is correct
6 Correct 6 ms 2304 KB Output is correct

Subtask #5
3.15 / 3.15

# Verdict Execution time Memory Grader output
1 Correct 10 ms 4224 KB Output is correct
2 Correct 9 ms 3944 KB Output is correct
3 Correct 9 ms 4148 KB Output is correct
4 Correct 8 ms 3840 KB Output is correct
5 Correct 7 ms 3072 KB Output is correct
6 Correct 6 ms 2432 KB Output is correct

Subtask #6
3.15 / 3.15

# Verdict Execution time Memory Grader output
1 Correct 8 ms 3840 KB Output is correct
2 Correct 7 ms 2944 KB Output is correct
3 Correct 7 ms 3072 KB Output is correct
4 Correct 8 ms 4096 KB Output is correct
5 Correct 7 ms 2944 KB Output is correct
6 Correct 9 ms 4224 KB Output is correct

Subtask #7
2.1 / 2.1

# Verdict Execution time Memory Grader output
1 Correct 9 ms 4224 KB Output is correct
2 Correct 9 ms 4224 KB Output is correct
3 Correct 9 ms 4224 KB Output is correct
4 Correct 9 ms 4224 KB Output is correct