Submission #670377

#	Time	Username	Problem	Language	Result	Execution time	Memory
670377		dozer	Coin Collecting (JOI19_ho_t4)	C++14	37 / 100	127 ms	152500 KiB

joi2019_ho_t4

#include <bits/stdc++.h>
using namespace std;
#define fileio() freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout)
#define fastio() cin.tie(0), ios_base::sync_with_stdio(0)
#define pb push_back
#define pii pair<int, int>
#define st first
#define nd second
#define endl "\n"
#define sp " "
#define N 3005
#define int long long

int dp[N][N];
vector<pii> p;
int n;
const int INF = 1e18 + 7;

int f(int i, int j)
{
	int curr = i + j + 1;
	if (curr > 2 * n) return 0;
	if (dp[i][j] != -1) return dp[i][j];
	int x = p[curr - 1].st;
	int  y = p[curr - 1].nd;
	int t1 = INF, t2 = INF;
	if (i != n) t1 = f(i + 1, j) + abs(x - (i + 1)) + abs(y - 1);
	if (j != n) t2 = f(i, j + 1) + abs(x - (j + 1)) + abs(y - 2);
	return dp[i][j] = min(t1, t2);
}

int32_t main()
{
	fastio();

	memset(dp, -1, sizeof(dp));
	cin>>n;
	for (int i = 1; i <= 2 * n; i++)
	{
		int x, y;
		cin>>x>>y;
		p.pb({x, y});
	}

	sort(p.begin(), p.end());
	cout<<f(0, 0)<<endl;

	cerr<<"time taken : "<<(float)clock() / CLOCKS_PER_SEC<<" seconds\n";
}

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