Submission #108750

#	Time	Username	Problem	Language	Result	Execution time	Memory
108750		tictaccat	Coin Collecting (JOI19_ho_t4)	C++14	37 / 100	203 ms	72668 KiB

joi2019_ho_t4

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

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