Pagini recente » Monitorul de evaluare | Cod sursa (job #318676) | Cod sursa (job #2542342) | Cod sursa (job #2320938) | Cod sursa (job #3302656)
// Ilie "The-Winner" Dumitru
// Dumnezeu sa o ierte
#include<bits/stdc++.h>
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
using ll=long long;
constexpr int NMAX=605;
constexpr ll MOD=1000000007;
ll MinAssignment(const std::vector<std::vector<ll> >& W) {
int n=sz(W), m=sz(W[0]); // assert(n <= m);
std::vector<ll> v(m), dist(m); // v: potential
std::vector<int> L(n, -1), R(m, -1); // matching pairs
std::vector<int> idx(m), prev(m); std::iota(all(idx), 0);
ll w, h; int j, l, s, t; auto reduce=[&]() { if(s==t) {
l=s; w=dist[idx[t++]]; for(int k=t;k<m;++k) { j=idx[k];
h=dist[j]; if(h>w) { continue; } if(h<w) t=s, w=h;
idx[k]=idx[t]; idx[t++]=j; } for(int k=s;k<t;++k) {
j=idx[k]; if(R[j]<0) return 1; } }
int q=idx[s++], p=R[q], k; for(k=t;k<m;++k) { j=idx[k];
h=W[p][j]-W[p][q]+v[q]-v[j]+w; if(h<dist[j]) {
dist[j]=h; prev[j]=p; if(h==w) { if(R[j]<0) return 1;
idx[k]=idx[t]; idx[t++]=j; } } } return 0; };
for(int i=0;i<n;++i) { for(int k=0;k<m;++k)
dist[k]=W[i][k]-v[k], prev[k]=i;
s=t=0; while(!reduce());
for(int k=0;k<l;++k) v[idx[k]]+=dist[idx[k]]-w;
for(int k=-1;k!=i;) R[j]=k=prev[j], std::swap(j, L[k]); }
ll ret=0; for(int i=0;i<n;++i) ret+=W[i][L[i]];
return ret; } // (i, L[i]) is a solution
ll oo=1LL<<50;
std::vector<std::vector<ll> > W;
int N;
int v[NMAX], aux[NMAX];
std::map<int, std::vector<int> > poss;
int main()
{
FILE* f=fopen("barman.in", "r"), *g=fopen("barman.out", "w");
int i, j;
ll ans=oo;
fscanf(f, "%d", &N);
W.resize(N);
for(i=0;i<N;++i)
{
fscanf(f, "%d", v+i);
aux[i]=v[i];
W[i].resize(N);
}
std::sort(aux, aux+N);
for(i=0;i<N;++i)
poss[aux[i]].push_back(i);
for(i=0;i<N;++i)
{
std::rotate(v, v+1, v+N);
for(j=0;j<N;++j)
std::fill(all(W[j]), oo);
for(j=0;j<N;++j)
{
for(int p : poss[v[j]])
{
if(j==p)
W[j][p]=0;
else if(j<p)
W[j][p]=20+std::min(p-j, N+j-p);
else
W[j][p]=20+std::min(j-p, N+p-j);
}
}
ans=std::min(ans, MinAssignment(W));
}
fprintf(g, "%lld\n", ans);
fclose(f);
fclose(g);
return 0;
}