oj.uz

Submission #855731

# Submission time Handle Problem Language Result Execution time Memory
855731 2023-10-01T17:24:22 Z denniskim Coin Collecting (JOI19_ho_t4) C++17
8 / 100
 10 ms 16732 KB 
#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[1010][1010];
pll a[2010];

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;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 460 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 756 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 600 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 344 KB Output is correct
21 Correct 1 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 0 ms 460 KB Output is correct
26 Correct 0 ms 348 KB Output is correct
27 Correct 0 ms 348 KB Output is correct
28 Correct 1 ms 348 KB Output is correct
29 Correct 0 ms 348 KB Output is correct
30 Correct 0 ms 348 KB Output is correct
31 Correct 0 ms 348 KB Output is correct
32 Correct 0 ms 348 KB Output is correct
33 Correct 0 ms 348 KB Output is correct

Subtask #2
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 460 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 756 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 600 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 344 KB Output is correct
21 Correct 1 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 0 ms 460 KB Output is correct
26 Correct 0 ms 348 KB Output is correct
27 Correct 0 ms 348 KB Output is correct
28 Correct 1 ms 348 KB Output is correct
29 Correct 0 ms 348 KB Output is correct
30 Correct 0 ms 348 KB Output is correct
31 Correct 0 ms 348 KB Output is correct
32 Correct 0 ms 348 KB Output is correct
33 Correct 0 ms 348 KB Output is correct
34 Runtime error 10 ms 16732 KB Execution killed with signal 11
35 Halted 0 ms 0 KB -

Subtask #3
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 460 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 756 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 600 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 344 KB Output is correct
21 Correct 1 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 0 ms 460 KB Output is correct
26 Correct 0 ms 348 KB Output is correct
27 Correct 0 ms 348 KB Output is correct
28 Correct 1 ms 348 KB Output is correct
29 Correct 0 ms 348 KB Output is correct
30 Correct 0 ms 348 KB Output is correct
31 Correct 0 ms 348 KB Output is correct
32 Correct 0 ms 348 KB Output is correct
33 Correct 0 ms 348 KB Output is correct
34 Runtime error 10 ms 16732 KB Execution killed with signal 11
35 Halted 0 ms 0 KB -