Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- typedef long long ll;
- const int mod = 1e9 + 7;
- int main() {
- ios_base::sync_with_stdio(false);
- cin.tie(0);
- cout.tie(0);
- int n;
- cin >> n;
- vector<pair<int, int>> a(52, {100, -100});
- vector<pair<int, int>> dp(52, {1e9, 1e9});
- vector<bool> flag(51);
- for(int i = 0; i < n; ++i){
- int x, y;
- cin >> x >> y;
- flag[y] = true;
- a[y].first = min(x, a[y].first);
- a[y].second = max(x, a[y].second);
- }
- int st = -1;
- for(int i = 1; i <= 50; ++i){
- if(flag[i]){
- dp[i].first = abs(i - 1) + abs(a[i].second - 1) + abs(a[i].second - a[i].first);
- dp[i].second = abs(i - 1) + abs(a[i].first - 1) + abs(a[i].second - a[i].first);
- st = i + 1;
- break;
- }
- }
- int pr = st - 1;
- for(int i = st; i <= 50; ++i){
- if(flag[i]){
- dp[i].first = min(dp[pr].first + abs(i - pr) + abs(a[i].second - a[pr].first) + abs(a[i].second - a[i].first), dp[i].first);
- dp[i].first = min(dp[i].first, dp[pr].second + abs(i - pr) + abs(a[i].second - a[pr].second) + abs(a[i].second - a[i].first));
- dp[i].second = min(dp[pr].first + abs(i - pr) + abs(a[i].first - a[pr].first) + abs(a[i].second - a[i].first), dp[i].second);
- dp[i].second = min(dp[i].second, dp[pr].second + abs(i - pr) + abs(a[i].first - a[pr].second) + abs(a[i].second - a[i].first));
- pr = i;
- }
- }
- cout << min(dp[pr].first, dp[pr].second) << "\n";
- }
Advertisement
Add Comment
Please, Sign In to add comment