Submission #1116030

#TimeUsernameProblemLanguageResultExecution timeMemory
1116030Dan4LifeCoin Collecting (JOI19_ho_t4)C++17
8 / 100
132 ms15000 KiB
#include <bits/stdc++.h> using namespace std; #define int long long const int N = (int)1e6+1e5; const int LINF = (int)2e18; int n, x[N], y[N]; array<int,2> a[N]; int dp[N]; int32_t main(){ ios_base::sync_with_stdio(false); cin.tie(0); cin >> n; n*=2; for(int i = 0; i < n; i++) cin >> x[i] >> y[i]; for(int i = 1; i <= n; i+=2) a[i] = {i/2+1,1}, a[i+1] = {i/2+1,2}; dp[0] = 0; for(int mask = 1; mask < (1<<n); mask++){ int num = __builtin_popcount(mask); dp[mask] = LINF; for(int i = 0; i < n; i++){ if(mask>>i&1){ dp[mask] = min(dp[mask], dp[mask^(1<<i)] +abs(a[num][0]-x[i])+abs(a[num][1]-y[i])); } } } cout << dp[(1<<n)-1] << "\n"; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...