Submission #855732

#TimeUsernameProblemLanguageResultExecution timeMemory
855732denniskimCoin Collecting (JOI19_ho_t4)C++17
37 / 100
2303 ms274432 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef __int128 lll; typedef long double ld; typedef pair<ll, ll> pll; typedef pair<ld, ld> pld; #define MAX 9223372036854775807LL #define MIN -9223372036854775807LL #define INF 0x3f3f3f3f3f3f3f3f #define fi first #define se second #define fastio ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cout << fixed; cout.precision(10); #define sp << " " #define en << "\n" #define compress(v) sort(v.begin(), v.end()), v.erase(unique(v.begin(), v.end()), v.end()) ll n; ll dp[5010][5010]; pll a[5010]; ll dist(ll x1, ll y1, ll x2, ll y2) { return abs(x1 - x2) + abs(y1 - y2); } bool comp(pll X, pll Y) { return make_pair(X.se, X.fi) < make_pair(Y.se, Y.fi); } int main(void) { fastio cin >> n; for(ll i = 1 ; i <= n * 2 ; i++) cin >> a[i].fi >> a[i].se; sort(a + 1, a + 1 + n * 2); for(ll i = 0 ; i <= n ; i++) { for(ll j = 0 ; j <= n ; j++) dp[i][j] = INF; } dp[0][0] = 0; for(ll i = 1 ; i <= n * 2 ; i++) { for(ll j = 0 ; j < i ; j++) { ll k = i - 1 - j; if(j + 1 <= n) dp[j + 1][k] = min(dp[j + 1][k], dp[j][k] + dist(j + 1, 1, a[i].fi, a[i].se)); if(k + 1 <= n) dp[j][k + 1] = min(dp[j][k + 1], dp[j][k] + dist(k + 1, 2, a[i].fi, a[i].se)); } } cout << dp[n][n]; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...