Cod sursa(job #2605552)

Utilizator mihai50000Mihai-Cristian Popescu mihai50000 Data 25 aprilie 2020 13:48:27
Problema Barman Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.16 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("barman.in");
ofstream fout("barman.out");

const int INF = 1e9;
const int DIM = 607;

vector <int> aux;

int v[DIM];
int p[DIM];

int dif = 0;

vector <int> pos1[DIM];
vector <int> pos2[DIM];

int solve(int n)
{
	for(int i = 1; i <= dif; ++i)
	{
		pos1[i].clear();
		pos2[i].clear();
	}
	
	for(int i = 1; i <= n; ++i)
	{
		if(p[i] != v[i])
		{
			pos1[v[i]].emplace_back(i);
			pos2[p[i]].emplace_back(i);
		}
	}
	
	int cost = 0;
	
	for(int i = 1; i <= dif; ++i)
	{
		for(int j = 0; j < pos1[i].size(); ++j)
			cost += 20 + abs(pos1[i][j] - pos2[i][j]);
	}
	
	return cost;
}

main()
{
	int n;
	fin >> n;
	
	for(int i = 1; i <= n; ++i)
	{
		fin >> v[i];
		aux.emplace_back(v[i]);
	}
	
	sort(aux.begin(), aux.end());
	aux.erase(unique(aux.begin(), aux.end()), aux.end());
	
	dif = aux.size();
	
	for(int i = 1; i <= n; ++i)
	{
		v[i] = lower_bound(aux.begin(), aux.end(), v[i]) - aux.begin() + 1;
		p[i] = v[i];
	}
	
	sort(p + 1, p + 1 + n);
	
	int ans = INF;
	
	for(int i = 1; i <= n; ++i)
	{
		ans = min(ans, solve(n));
		
		for(int j = n + 1; j >= 1; --j)
			p[j] = p[j - 1];
		
		p[1] = p[n + 1];
	}
	
	fout << ans << '\n';
}