Submission #252747

#	Time	Username	Problem	Language	Result	Execution time	Memory
252747		Mlxa	Coin Collecting (JOI19_ho_t4)	C++14	37 / 100	35 ms	32388 KiB

joi2019_ho_t4

#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define x first
#define y second
using namespace std;
using ll  = long long;
#define int ll

void umin(int &a, int b) {
	a = min(a, b);
}
void umax(int &a, int b) {
	a = max(a, b);
}


const int N		= 2020;
const int INF 	= 1e18;

int n;
int x[N];
int y[N];
int p[N];
int w[N];
int dp[N][N];

int f(int i, int fx, int fy) {
	return abs(x[i] - fx) + abs(y[i] - fy);
}

signed main() {
#ifdef LC
    assert(freopen("input.txt", "r", stdin));
#endif
    ios::sync_with_stdio(0), cin.tie(0);
	cin >> n;
	for (int i = 0; i < 2 * n; ++i) {
		cin >> x[i] >> y[i];
		p[i] = i;
	}
	sort(p, p + 2 * n, [&](int i, int j) {
		return x[i] < x[j];
	});
	for (int i = 0; i < 2 * n; ++i) {
		w[p[i]] = i;
	}
	for (int i = 0; i < 2 * n; ++i) {
		while (w[i] != i) {
			int j = w[i];
			swap(w[i], w[j]);
			swap(x[i], x[j]);
			swap(y[i], y[j]);
		}
	}
	assert(is_sorted(x, x + 2 * n));
	fill_n(dp[0], N * N, INF);
	dp[0][0] = 0;
	for (int i = 0; i <= n; ++i) {
		for (int j = 0; j <= n; ++j) {
			if (i < n) {
				umin(dp[i + 1][j], dp[i][j] + f(i + j, i + 1, 1));
			}
			if (j < n) {
				umin(dp[i][j + 1], dp[i][j] + f(i + j, j + 1, 2));
			}
		}
	}
	cout << dp[n][n] << "\n";
    return 0;
}

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