제출 #532972

#제출 시각아이디문제언어결과실행 시간메모리
532972amunduzbaevCoin Collecting (JOI19_ho_t4)C++17
8 / 100
176 ms8524 KiB
#include "bits/stdc++.h"
using namespace std;

#define ar array
#define int long long

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	int n; cin>>n; n <<= 1;
	vector<ar<int, 2>> a(n), b(n);
	for(int i=0;i<n;i++){
		cin>>a[i][0]>>a[i][1];
		b[i][0] = i / 2 + 1, b[i][1] = (i&1) + 1;
	}
	vector<int> dp(1 << n, 1e15);
	dp[0] = 0;
	for(int mask=1;mask < (1 << n);mask++){
		int in = __builtin_popcount(mask) - 1;
		for(int i=0;i<n;i++){
			if(mask >> i & 1){
				dp[mask] = min(dp[mask], dp[mask ^ (1 << i)] + 
				abs(a[i][0] - b[in][0]) + abs(a[i][1] - b[in][1]));
			}
		}
	}
	
	cout<<dp[(1 << n) - 1]<<"\n";
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...