Submission #532972

#	Time	Username	Problem	Language	Result	Execution time	Memory
532972		amunduzbaev	Coin Collecting (JOI19_ho_t4)	C++17	8 / 100	176 ms	8524 KiB

joi2019_ho_t4

#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";
}

• Subtask 1: 8 / 8
• Subtask 2: 0 / 29
• Subtask 3: 0 / 63