Submission #1100224

#TimeUsernameProblemLanguageResultExecution timeMemory
1100224vjudge1Coin Collecting (JOI19_ho_t4)C++98
37 / 100
36 ms35632 KiB
#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];
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...