Submission #1317810

#TimeUsernameProblemLanguageResultExecution timeMemory
1317810JuanJLCoin Collecting (JOI19_ho_t4)C++20
0 / 100
157 ms339968 KiB
#include <bits/stdc++.h>

#define fst first
#define snd second
#define pb push_back
#define forn(i,a,b) for(int i = a; i<b; i++)
#define SZ(x) (int)x.size()
#define ALL(x) x.begin(),x.end()
#define mset(a,v) memset(a,v,sizeof(a))
#define FIN ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
typedef long long ll;

const int rMAXN = 21;

ll dp[rMAXN][1<<rMAXN];

ll n;
pair<ll,ll> p[rMAXN];

ll f(ll x, ll y){
	ll &res = dp[x][y];
	if(res!=-1) return res;
	if(x==2*n) return 0;
	
	res = 10000000000000000;
	forn(i,0,2*n) if(!(y&(1<<i))){
		ll cost = 0;
		
		cost+=abs(p[i].fst-(1+x/2));
		cost+=abs(p[i].snd-(1+(x%2)));

		//cout<<x<<" "<<i<<" "<<cost<<'\n';
	
		res=min(res,f(x+1,y|(1<<i))+cost);
	}

	return res;
}

int main(){ FIN;
	cin>>n;
	forn(i,0,2*n){
		cin>>p[i].fst>>p[i].snd;
	}

	mset(dp,-1);

	ll res = f(0,0);

	if(res==10000000000000000){
		cout<<-1<<'\n';
	}else{
		cout<<res<<'\n';
	}
	
	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...