제출 #883169

#제출 시각아이디문제언어결과실행 시간메모리
883169NotLinuxCoin Collecting (JOI19_ho_t4)C++17
37 / 100
199 ms274432 KiB
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int inf = 1e18 + 7;//wa alırsa bunu değiştir !!!
inline int dist(pair < int , int > a , pair < int , int > b){
	return abs(a.first-b.first) + abs(a.second-b.second);
}
void solve(){
	int n;cin >> n;
	pair < int , int > point[2*n];
	for(int i = 0;i<2*n;i++){
		cin >> point[i].first >> point[i].second;
	}
	sort(point , point + 2*n);
	//cout << "points : ";for(int i = 0;i<2*n;i++)cout << point[i].first << "," << point[i].second << "    ";cout << endl;
	int dp[2*n+1][n+1];
	for(int i = 0;i<=2*n;i++){
		for(int j = 0;j<=n;j++){
			dp[i][j] = inf;
		}
	}
	dp[0][0] = 0;
	for(int i = 1;i<=2*n;i++){
		for(int j = 0;j<=min(i,n);j++){
			//önceki üst satıra geldi
			if(j != 0){
				dp[i][j] = min(dp[i][j] , dp[i-1][j-1] + dist(point[i-1],{j,2}) );
			}
			//önceki alt satıra geldi
			dp[i][j] = min(dp[i][j] , dp[i-1][j] + dist(point[i-1],{i-j,1}) );
			//cout << i << " " << j << " : " << dp[i][j] << endl;
		}
	}
	cout << dp[2*n][n] << endl;
}
signed main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	int testcase = 1;//cin >> testcase;
	while(testcase--)solve();
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...