Submission #1100224

#	Time	Username	Problem	Language	Result	Execution time	Memory
1100224		vjudge1	Coin Collecting (JOI19_ho_t4)	C++98	37 / 100	36 ms	35632 KiB

joi2019_ho_t4

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e18;
pair<int, int> a[100001];
int dp[4000][2000];
signed main()
{
    int n;
	cin >> n;
	for(int i = 0; i < 2 * n; i++)
	{
	    cin >> a[i].first >> a[i].second;
	}
	sort(a, a + 2 * n);
	for(int i = 1; i <= n; i++)
	{
	    dp[0][i] = N;
	}
	dp[0][0] = 0;
	for(int i = 1; i <= 2 * n; i++)
	{
		for(int j = 0; j <= n; j++)
		{
		    dp[i][j] = N;
		}
		for(int j = max(0LL, i - n); j <= i && j <= n; j++)
		{
			dp[i][j] = min(dp[i][j], dp[i - 1][j] + abs(a[i - 1].first - i + j) + abs(a[i - 1].second - 1));
			if(j)
			{
			    dp[i][j] = min(dp[i][j], dp[i - 1][j - 1] + abs(a[i - 1].first - j) + abs(a[i - 1].second - 2));
			}
		}
	}
	cout << dp[n * 2][n];
}

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