Submission #108750

#TimeUsernameProblemLanguageResultExecution timeMemory
108750tictaccatCoin Collecting (JOI19_ho_t4)C++14
37 / 100
203 ms72668 KiB
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const ll INF = 1e9;
const int MAX = 1000 + 10;

int N;
ll d0;
vector<vector<ll>> dp(MAX*2,vector<ll>(MAX*2,INF));
vector<pair<ll,ll>> p;

int main() {

    cin >> N;

    for (int i = 0; i < 2*N; i++) {
        ll X,Y,x,y; cin >> X >> Y;
        if (Y <= 1) y = 1;
        else y = 2;
        
        if (X <= 1) x = 1;
        else if (1 < X && X < N) x = X;
        else x = N;

        p.push_back(make_pair(x,y));
        d0 += abs(Y-y)+abs(X-x);
    }

    sort(p.begin(),p.end());

    // for (auto t: p) {
    //     cout << t.first << " " << t.second << "\n";
    // }

    dp[0][0] = 0;

    for (int i = 1; i <= 2*N; i++) {
        ll x,y; tie(x,y) = p[i-1];
        for (int a = 0; a <= i; a++) {
            dp[i][a] = dp[i-1][a] + abs(x-(i-a)) + abs(y-2);
            if (a > 0) dp[i][a] = min(dp[i][a],dp[i-1][a-1] + abs(x - a) + abs(y-1));
        }
    }

    cout << d0 + *min_element(dp[2*N].begin(),dp[2*N].begin()+2*N) << "\n";

    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...