Submission #222379

#	Time	Username	Problem	Language	Result	Execution time	Memory
222379		compilers	앱 (KOI13_app)	C++14	6.30 / 21	1105 ms	150264 KiB

app

#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
• Subtask 2: 3.15 / 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