Cod sursa(job #348774)

Utilizator andrei-alphaAndrei-Bogdan Antonescu andrei-alpha Data 16 septembrie 2009 20:07:07
Problema Barman Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.8 kb
using namespace std;

#include <set>
#include <map>
#include <list>
#include <deque>
#include <stack>
#include <queue>
#include <cmath>
#include <cctype>
#include <cstdio>
#include <vector>
#include <string>
#include <bitset>
#include <utility>
#include <iomanip>
#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <functional>

#define pb push_back
#define size(V) ((int)(V.size()))
#define f first
#define s second
#define II inline
#define ll long long
#define db double
#define FOR(i,a,b) for(int i=a;i<=b;++i)
#define all(v) v.begin() , v.end()
#define CC(v) memset((v),0,sizeof((v)))
#define CP(v,w) memcpy((v),(w),sizeof((w)))
#define mp make_pair
#define mod 654321
#define oo 1<<30

#define IN "barman.in"
#define OUT "barman.out"
#define N_MAX 1<<10

typedef vector<int> VI;
typedef pair<int,int> pi;
typedef vector<string> VS;
template<class T> string toString(T n) {ostringstream ost;ost<<n;ost.flush();return ost.str();}
typedef vector<string> VS;

int N;
int V[N_MAX],A[N_MAX];
vector<pi> Vp,Ap;

II void scan()
{
	freopen(IN,"r",stdin);
	freopen(OUT,"w",stdout);
	scanf("%d\n",&N);
	
	FOR(i,1,N)
		scanf("%d",V+i);
}

II void solve()
{
	CP(A,V);
	sort(A+1,A+N+1);
	
	int rez(oo);
	
	FOR(i,1,N)
	{
		Vp.resize(0);
		Ap.resize(0);
		
		FOR(j,1,N)
			if(V[j] ^ A[j])
			{
				Vp.pb( mp(V[j],j) );
				Ap.pb( mp(A[j],j) );
			}
		
		sort(Vp.begin(),Vp.end() );
		sort(Ap.begin(),Ap.end() );
		
		int cost = 0;
		FOR(j,0,size(Vp)-1)
			cost += max(Vp[j].s - Ap[j].s,Ap[j].s - Vp[j].s);
		cost += size(Vp) * 20;
		
		rez = min(rez,cost);
		
		int aux = A[N];
		for(int i = N;i >= 1;--i)
			A[i] = A[i-1];
		A[1] = aux;
	}
	
	printf("%d\n",rez);
}

int main()
{
	scan();
	solve();
	return 0;
}