Submission #429537

#	Time	Username	Problem	Language	Result	Execution time	Memory
429537		Berted	Coin Collecting (JOI19_ho_t4)	C++14	0 / 100	2 ms	460 KiB

joi2019_ho_t4

#include <iostream>
#include <algorithm>
#include <cassert>
#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];
bool opt[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; opt[0][0] = 1;
 
	for (int i = 1; i <= 2 * N; i++)
	{
		ll val = INF;
		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));
			val = min(val, DP[i][j]);

			//cerr << i << " " << j << " " << DP[i][j] << "\n";
		}
		
		bool yes = 0;

		for (int j = 0; j <= N; j++)
		{
			if (DP[i][j] == val) 
			{
				bool tes = opt[i - 1][j];
				if (j) tes |= opt[i - 1][j - 1];
				opt[i][j] = tes;
				yes |= tes;
			}
		}

		assert(yes);
	}
 
	cout << DP[2 * N][N] << "\n";
	return 0;
}

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