Submission #1125827

#	Time	Username	Problem	Language	Result	Execution time	Memory
1125827		Pwo	Coin Collecting (JOI19_ho_t4)	C++17	37 / 100	629 ms	8640 KiB

joi2019_ho_t4

#include <bits/stdc++.h>
using namespace std;
#define int long long

int n, dp[1005][1005];
pair<int, int> a[2005];

int32_t main() {
	ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> n;
	for (int i = 1; i <= n + n; i++) cin >> a[i].first >> a[i].second;
	sort(a + 1, a + n + n + 1);
	for (int i = 0; i <= n; i++) for (int j = 0; j <= n; j++) {
		if (i == 0 && j == 0) continue;
		dp[i][j] = min(
			(i > 0 ? dp[i - 1][j] + abs(i - a[i + j].first) + abs(a[i + j].second - 1) : 1e18),
			(j > 0 ? dp[i][j - 1] + abs(j - a[i + j].first) + abs(a[i + j].second - 2) : 1e18)
		);
	}
	cout << dp[n][n];
}

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