Submission #161286

#	Time	Username	Problem	Language	Result	Execution time	Memory
161286		pr3pony	Coin Collecting (JOI19_ho_t4)	C++14	37 / 100	31 ms	8956 KiB

joi2019_ho_t4

#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*2];
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;
}

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