oj.uz

Submission #222379

# Submission time Handle Problem Language Result Execution time Memory
222379 2020-04-13T05:51:56 Z compilers 앱 (KOI13_app) C++14
6.3 / 21
 1000 ms 150264 KB 
#include	<iostream>
#include	<algorithm>
#include	<vector>
#include	<map>

using namespace	std;

#define	MAX_SIZE	(100+1)

typedef	pair<int,int>	App;	// first:used_memory, second:cost

int			N,M;
vector<App>	app;

map<int,int>	mem_table[MAX_SIZE];	// <free_memory,cost>

void	input(int& initial_free_memory)
{
	int	memory[MAX_SIZE];
	
	cin>>N>>M;
	app.push_back(make_pair(0,0));
	
	for(int i=1;i<=N;i++)
	{
		cin>>memory[i];
	}
	
	for(int i=1;i<=N;i++)
	{
		int	c;
		
		cin>>c;
		
		if( c == 0 )
		{
			initial_free_memory += memory[i];
		}
		else
		{
			app.push_back(make_pair(memory[i],c));
		}
	}
}

int		deactivate_app(int required_memory)
{
	map<int,int>::iterator	it;
	int						num_of_apps,ret;
	
	num_of_apps = app.size()-1;
	ret = 0x7FFFFFFF;
	
	for(int i=1;i<=num_of_apps;i++)
	{
		mem_table[i][app[i].first] = app[i].second;
		
		for(it=mem_table[i-1].begin();it!=mem_table[i-1].end();it++)
		{
			const int&	prev_memory = it->first;
			const int&	prev_cost = it->second;
			
			if( mem_table[i][prev_memory]==0 || 
				mem_table[i][prev_memory]>prev_cost )
			{
				mem_table[i][prev_memory] = prev_cost;
			}
			
			if( prev_memory < required_memory )
			{
				int	current_free_memory,current_cost;
				
				current_free_memory = prev_memory+app[i].first;
				current_cost = prev_cost+app[i].second;
				
				if( mem_table[i][current_free_memory]==0 || 
					mem_table[i][current_free_memory]>current_cost )
				{
					mem_table[i][current_free_memory] = current_cost;
				}
			}
		}
	}
	
	map<int,int>&	last_app = mem_table[num_of_apps];
	
	for(it=last_app.begin();it!=last_app.end();it++)
	{
		const int&	free_memory = it->first;
		const int&	free_cost = it->second;
		
		if( free_memory < required_memory )
		{
			continue;
		}
		
		ret = min(free_cost,ret);
	}
	
	return	ret;
}

int		main(void)
{
	int	size_of_free_memory_without_cost;
	
	size_of_free_memory_without_cost = 0;
	input(size_of_free_memory_without_cost);
	
	if( size_of_free_memory_without_cost >= M )
	{
		cout<<"0\n";
	}
	else
	{
		cout<<deactivate_app(M-size_of_free_memory_without_cost)<<'\n';
	}
	
	return	0;
}

Subtask #1
3.15 / 3.15

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 25 ms 3584 KB Output is correct
3 Correct 42 ms 5624 KB Output is correct
4 Correct 7 ms 896 KB Output is correct
5 Correct 5 ms 256 KB Output is correct
6 Correct 7 ms 768 KB Output is correct

Subtask #2
3.15 / 3.15

# Verdict Execution time Memory Grader output
1 Correct 4 ms 256 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 4 ms 256 KB Output is correct

Subtask #3
0 / 3.15

# Verdict Execution time Memory Grader output
1 Correct 791 ms 86152 KB Output is correct
2 Correct 36 ms 5624 KB Output is correct
3 Correct 571 ms 68540 KB Output is correct
4 Execution timed out 1098 ms 109504 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
0 / 3.15

# Verdict Execution time Memory Grader output
1 Correct 12 ms 1792 KB Output is correct
2 Execution timed out 1103 ms 112248 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 3.15

# Verdict Execution time Memory Grader output
1 Execution timed out 1099 ms 150264 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 3.15

# Verdict Execution time Memory Grader output
1 Execution timed out 1105 ms 147960 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 2.1

# Verdict Execution time Memory Grader output
1 Execution timed out 1105 ms 133368 KB Time limit exceeded
2 Halted 0 ms 0 KB -