Submission #161285

#TimeUsernameProblemLanguageResultExecution timeMemory
161285pr3ponyCoin Collecting (JOI19_ho_t4)C++14
8 / 100
3 ms632 KiB
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define F first
#define S second
const int N = 1087;
const ll inf = 9e18;
pii p[N];
ll f(int i,int x,int y)
{
    return abs(x-p[i].F) + abs(y-p[i].S);
}
ll dp[N][N];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    ll ans = 0;
    int n;
    cin >> n;
    for (int i = 1; i <= 2*n; ++i) {
        int x,y;
        cin >> x >> y;
        if (x < 1) ans += 1 - x, x = 1;
        if (x > n) ans += x - n, x = n;
        if (y < 1) ans += 1 - y, y = 1;
        if (y > 2) ans += y - 2, y = 2;
        p[i] = {x, y};
    }
    sort(p+1,p+1+2*n);
    for (int t = 1; t <= 2*n; ++t)
        for (int i = 0; i <= min(n,t); ++i) {
            int j = t - i;
            if (j > n)
                continue;
            dp[i][j] = inf;
            if (i)
                dp[i][j] = min(dp[i][j], dp[i-1][j] + f(t,i,1));
            if (j)
                dp[i][j] = min(dp[i][j], dp[i][j-1] + f(t,j,2));
        }
    cout << ans + dp[n][n] << endl;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...