# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
1151197 | KK_1729 | Coin Collecting (JOI19_ho_t4) | Pypy 3 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define pb push_back
#define all(a) a.begin(), a.end()
#define endl "\n"
void printVector(vector<int> a){
for (auto x: a) cout << x << " ";
cout << endl;
}
int dist(pair<int,int> x, pair<int, int> y){
return abs(x.first-y.first)+abs(x.second-y.second);
}
void solve(){
int n; cin >> n;
vector<pair<int, int>> points = {{-10000000000000,-1}};
FOR(i,0,2*n){
int x, y; cin >> x >> y;
points.pb({x, y});
}
sort(all(points));
vector<vector<int>> dp(n+10, vector<int>(n+10, 1e16));
dp[0][0] = 0;
FOR(i,0,n+1){
FOR(j,0,n+1){
if (i+j >= 2*n) continue;
dp[i][j+1] = min(dp[i][j+1], dp[i][j]+dist(points[i+j+1], {j+1, 2}));
dp[i+1][j] = min(dp[i+1][j], dp[i][j]+dist(points[i+j+1], {i+1, 1}));
}
}
cout << dp[n][n] << endl;
}
int32_t main(){
ios::sync_with_stdio(false);cin.tie(nullptr);
int t = 1; // cin >> t;
while (t--) solve();
}