제출 #1328836

#제출 시각아이디문제언어결과실행 시간메모리
1328836boclobanchatCoin Collecting (JOI19_ho_t4)C++20
8 / 100
4 ms3652 KiB
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+5;
const int MX=200;
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) continue;
	    	if(i&&j-i+MX+1<=MX*2) dp[i][p]=min(dp[i][p],dp[i-1][j-i+MX+1]+manhattan(A[i+j],(pair<long long,long long>){i,1}));
	    	if(j&&j-i+MX-1>=0) dp[i][p]=min(dp[i][p],dp[i][j-i+MX-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...