Submission #228312

#	Time	Username	Problem	Language	Result	Execution time	Memory
228312		kshitij_sodani	Coin Collecting (JOI19_ho_t4)	C++17	37 / 100	74 ms	17792 KiB

joi2019_ho_t4

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
typedef int64_t llo;
#define mp make_pair
#define pb push_back
#define a first
#define b second
llo it[100001][2];

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	llo n;
	cin>>n;
	memset(it,0,sizeof(it));
	vector<pair<llo,llo>> ac;
	llo aa,bb;
	llo ans=0;
	for(llo i=0;i<2*n;i++){
		cin>>aa>>bb;
		if(bb<=1){
			if(aa<1){
				it[0][0]+=1;
				ac.pb({0,0});
			}
			else if(aa>n){
				it[n-1][0]+=1;
				ac.pb({n-1,0});
			}
			else{
				it[aa-1][0]+=1;
				ac.pb({aa-1,0});
			}
		}
		else{
			if(aa<1){
				it[0][1]+=1;
				ac.pb({0,1});
			}
			else if(aa>n){
				it[n-1][1]+=1;
				ac.pb({n-1,1});
			}
			else{
				it[aa-1][1]+=1;
				ac.pb({aa-1,1});
			}
		}
		ans+=abs(aa-(ac[i].a+1))+abs(bb-(ac[i].b+1));
	//	cout<<ans<<endl;
	//	cout<<ac[ac.size()-1].a<<","<<ac[ac.size()-1].b<<endl;
	}
	//cout<<ans<<endl;
	sort(ac.begin(),ac.end());
	llo dp[2*n][n+1];
	for(llo i=0;i<2*n;i++){
		for(llo j=0;j<=n;j++){
			dp[i][j]=2*n*n;
		}
	}
	for(llo i=0;i<2*n;i++){
	//	cout<<ac[i].a<<":"<<ac[i].b<<endl;

		llo co=0;
		if(ac[i].b==1){
			co=1;
		}
		if(i==0){
			dp[0][0]=abs(ac[i].a)+1-co;
			dp[0][1]=abs(ac[i].a)+co;
		}
		else{
			if(i<n){
				dp[i][0]=dp[i-1][0]+abs(i-ac[i].a)+1-co;
			//	cout<<dp[i-1][0]<<i<<" "<<ac[i].a<<" "<<co<<endl;
			}
			for(llo j=1;j<=min(i+1,n);j++){
				if((i-j)>=0 and (i-j)<n){
					dp[i][j]=min(dp[i][j],dp[i-1][j]+abs((i-j)-ac[i].a)+1-co);
				}
				//if(j<n){
					dp[i][j]=min(dp[i][j],dp[i-1][j-1]+abs((j-1)-ac[i].a)+co);
				//}
			}
		}
	/*	for(llo j=0;j<=n;j++){
			cout<<dp[i][j]<<" ";
		}
		cout<<endl;*/
	}
	ans+=dp[2*n-1][n];
	cout<<ans<<endl;
	
	return 0;
}

• Subtask 1: 8 / 8
• Subtask 2: 29 / 29
• Subtask 3: 0 / 63