Submission #1318198

#TimeUsernameProblemLanguageResultExecution timeMemory
1318198JuanJLCoin Collecting (JOI19_ho_t4)C++20
8 / 100
14 ms8404 KiB
#include <bits/stdc++.h>

#define fst first
#define snd second
#define pb push_back
#define SZ(x) (int)x.size()
#define ALL(x) x.begin(),x.end()
#define forn(i,a,b) for(int i = a; i<b; i++)
#define mset(a,v) memset(a,v,sizeof(a))
#define FIN ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
typedef long long ll;

const int MAXN = 1000+5;

ll n;
ll dp[MAXN][MAXN];
vector<pair<ll,ll>> p;

ll f(ll x, ll y){
	ll &res=dp[x][y];
	if(res!=-1) return res;
	if(x==2*n && y==n) return 0;
	if(x==2*n) return 1000000000000000;

	res=1000000000000000;
	pair<ll,ll> p1 = {1+x-y,1};
	pair<ll,ll> p2 = {1+y,2};
	res=min(res,f(x+1,y+1)+abs(p[x].fst-p2.fst)+abs(p[x].snd-p2.snd));
	res=min(res,f(x+1,y)+abs(p[x].fst-p1.fst)+abs(p[x].snd-p1.snd));
	return res;
}

bool comp(const pair<ll,ll> &a, const pair<ll,ll> &b){
	if(a.fst<b.fst) return true;
	if(a.fst>b.fst) return false;
	if(abs(a.snd-1)<abs(b.snd-1)) return true;
	return false;
}

int main(){
	cin>>n;
	p.clear();
	p.resize(2*n); forn(i,0,2*n) cin>>p[i].fst>>p[i].snd;

	sort(ALL(p),comp);

	mset(dp,-1);

	ll res = f(0,0);
	if(res>=1000000000000000){
		cout<<-1<<'\n';
	}else cout<<res<<'\n';
	
	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...