Submission #1328848

#TimeUsernameProblemLanguageResultExecution timeMemory
1328848boclobanchatCoin Collecting (JOI19_ho_t4)C++20
8 / 100
2 ms1860 KiB
#include<bits/stdc++.h>
using namespace std;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
int Rand(int l,int r) { return uniform_int_distribution<int>(l,r)(rng); }
const int MAXN=2e5+5;
const int MX=100;
const long long INF=1e18;
struct node
{
	long long first,second,pos;
};
node A[MAXN];
long long dp[MAXN][MX*2+5];
int val[MAXN];
bool comp(node a,node b)
{
	if(a.first==b.first) return a.pos<b.pos;
	return a.first<b.first;
}
long long manhattan(node 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;
    	A[i].pos=i;
	}
	for(int i=1;i<=n*4;i++) swap(A[Rand(1,n*2)].pos,A[Rand(1,n*2)].pos);
    sort(A+1,A+n*2+1,comp);
    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...