Submission #1328842

#TimeUsernameProblemLanguageResultExecution timeMemory
1328842boclobanchatCoin Collecting (JOI19_ho_t4)C++20
8 / 100
1 ms456 KiB
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e3+5;
const int MX=500;
const long long INF=1e18;
pair<long long,long long> A[MAXN];
long long dp[MAXN][MX*2+5];
long long manhattan(pair<long long,long long> a,pair<long long,long long> b)
{
	return abs(a.first-b.first)+abs(a.second-b.second);
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin>>n;
    for(int i=1;i<=n*2;i++) cin>>A[i].first>>A[i].second;
    sort(A+1,A+n*2+1);
    for(int i=0;i<=n;i++) for(int p=0;p<=MX*2;p++)
    {
    	int j=i+p-MX;
    	dp[i][p]=INF;
    	if(i==0&&j==0) dp[i][p]=0;
	    else
	    {
			if(j<0||j>n) continue;
	    	if(i&&p+1<=MX*2) dp[i][p]=min(dp[i][p],dp[i-1][p+1]+manhattan(A[i+j],(pair<long long,long long>){i,1}));
	    	if(j&&p-1>=0) dp[i][p]=min(dp[i][p],dp[i][p-1]+manhattan(A[i+j],(pair<long long,long long>){j,2}));
		}
	}
	cout<<dp[n][MX];
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...