Submission #429191

#	Time	Username	Problem	Language	Result	Execution time	Memory
429191		Berted	Coin Collecting (JOI19_ho_t4)	C++14	37 / 100	71 ms	34724 KiB

joi2019_ho_t4

#include <iostream>
#include <algorithm>
#define pii pair<int, int>
#define fst first
#define snd second
#define ll long long

using namespace std;

const ll INF = 1e18;

int N;
pii A[100001];
ll DP[2001][1001];

int main()
{
	ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> N;
	for (int i = 0; i < 2 * N; i++) cin >> A[i].fst >> A[i].snd;
	sort(A, A + 2 * N);
	
	for (int i = 1; i <= N; i++) DP[0][i] = INF;
	DP[0][0] = 0;

	for (int i = 1; i <= 2 * N; i++)
	{
		for (int j = 0; j <= N; j++) DP[i][j] = INF;
		for (int j = max(0, i - N); j <= i && j <= N; j++)
		{
			DP[i][j] = min(DP[i][j], DP[i - 1][j] + abs(A[i - 1].fst - i + j) + abs(A[i - 1].snd - 1));
			if (j) DP[i][j] = min(DP[i][j], DP[i - 1][j - 1] + abs(A[i - 1].fst - j) + abs(A[i - 1].snd - 2));
		}
	}

	cout << DP[2 * N][N] << "\n";
	return 0;
}

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