Submission #1328822

#TimeUsernameProblemLanguageResultExecution timeMemory
1328822boclobanchatCoin Collecting (JOI19_ho_t4)C++20
37 / 100
9 ms12208 KiB
#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e3+5;
const long long INF=1e18;
pair<long long,long long> A[MAXN];
long long dp[MAXN][MAXN];
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 j=0;j<=n;j++) if(i==0&&j==0) dp[i][j]=0;
    else
    {
    	dp[i][j]=INF;
    	if(i) dp[i][j]=min(dp[i][j],dp[i-1][j]+manhattan(A[i+j],(pair<long long,long long>){i,1}));
    	if(j) dp[i][j]=min(dp[i][j],dp[i][j-1]+manhattan(A[i+j],(pair<long long,long long>){j,2}));
	}
	cout<<dp[n][n];
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...