oj.uz

Submission #1100224

# Submission time Handle Problem Language Result Execution time Memory
1100224 2024-10-13T10:15:03 Z vjudge1 Coin Collecting (JOI19_ho_t4) C++
37 / 100
 36 ms 35632 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e18;
pair<int, int> a[100001];
int dp[4000][2000];
signed main()
{
    int n;
	cin >> n;
	for(int i = 0; i < 2 * n; i++)
	{
	    cin >> a[i].first >> a[i].second;
	}
	sort(a, a + 2 * n);
	for(int i = 1; i <= n; i++)
	{
	    dp[0][i] = N;
	}
	dp[0][0] = 0;
	for(int i = 1; i <= 2 * n; i++)
	{
		for(int j = 0; j <= n; j++)
		{
		    dp[i][j] = N;
		}
		for(int j = max(0LL, i - n); j <= i && j <= n; j++)
		{
			dp[i][j] = min(dp[i][j], dp[i - 1][j] + abs(a[i - 1].first - i + j) + abs(a[i - 1].second - 1));
			if(j)
			{
			    dp[i][j] = min(dp[i][j], dp[i - 1][j - 1] + abs(a[i - 1].first - j) + abs(a[i - 1].second - 2));
			}
		}
	}
	cout << dp[n * 2][n];
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2384 KB Output is correct
2 Correct 1 ms 2384 KB Output is correct
3 Correct 1 ms 2384 KB Output is correct
4 Correct 1 ms 4432 KB Output is correct
5 Correct 1 ms 4432 KB Output is correct
6 Correct 1 ms 4432 KB Output is correct
7 Correct 1 ms 4600 KB Output is correct
8 Correct 1 ms 4436 KB Output is correct
9 Correct 1 ms 4540 KB Output is correct
10 Correct 1 ms 4436 KB Output is correct
11 Correct 1 ms 4436 KB Output is correct
12 Correct 1 ms 4436 KB Output is correct
13 Correct 1 ms 4600 KB Output is correct
14 Correct 1 ms 4436 KB Output is correct
15 Correct 1 ms 4604 KB Output is correct
16 Correct 1 ms 4436 KB Output is correct
17 Correct 1 ms 4436 KB Output is correct
18 Correct 1 ms 4436 KB Output is correct
19 Correct 1 ms 4436 KB Output is correct
20 Correct 1 ms 4436 KB Output is correct
21 Correct 1 ms 4436 KB Output is correct
22 Correct 1 ms 4436 KB Output is correct
23 Correct 1 ms 4436 KB Output is correct
24 Correct 1 ms 4436 KB Output is correct
25 Correct 1 ms 4436 KB Output is correct
26 Correct 1 ms 4600 KB Output is correct
27 Correct 1 ms 4436 KB Output is correct
28 Correct 1 ms 4436 KB Output is correct
29 Correct 1 ms 4436 KB Output is correct
30 Correct 1 ms 4436 KB Output is correct
31 Correct 1 ms 4436 KB Output is correct
32 Correct 1 ms 4436 KB Output is correct
33 Correct 1 ms 4436 KB Output is correct

Subtask #2
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2384 KB Output is correct
2 Correct 1 ms 2384 KB Output is correct
3 Correct 1 ms 2384 KB Output is correct
4 Correct 1 ms 4432 KB Output is correct
5 Correct 1 ms 4432 KB Output is correct
6 Correct 1 ms 4432 KB Output is correct
7 Correct 1 ms 4600 KB Output is correct
8 Correct 1 ms 4436 KB Output is correct
9 Correct 1 ms 4540 KB Output is correct
10 Correct 1 ms 4436 KB Output is correct
11 Correct 1 ms 4436 KB Output is correct
12 Correct 1 ms 4436 KB Output is correct
13 Correct 1 ms 4600 KB Output is correct
14 Correct 1 ms 4436 KB Output is correct
15 Correct 1 ms 4604 KB Output is correct
16 Correct 1 ms 4436 KB Output is correct
17 Correct 1 ms 4436 KB Output is correct
18 Correct 1 ms 4436 KB Output is correct
19 Correct 1 ms 4436 KB Output is correct
20 Correct 1 ms 4436 KB Output is correct
21 Correct 1 ms 4436 KB Output is correct
22 Correct 1 ms 4436 KB Output is correct
23 Correct 1 ms 4436 KB Output is correct
24 Correct 1 ms 4436 KB Output is correct
25 Correct 1 ms 4436 KB Output is correct
26 Correct 1 ms 4600 KB Output is correct
27 Correct 1 ms 4436 KB Output is correct
28 Correct 1 ms 4436 KB Output is correct
29 Correct 1 ms 4436 KB Output is correct
30 Correct 1 ms 4436 KB Output is correct
31 Correct 1 ms 4436 KB Output is correct
32 Correct 1 ms 4436 KB Output is correct
33 Correct 1 ms 4436 KB Output is correct
34 Correct 7 ms 35412 KB Output is correct
35 Correct 7 ms 35412 KB Output is correct
36 Correct 8 ms 35412 KB Output is correct
37 Correct 8 ms 35412 KB Output is correct
38 Correct 8 ms 35580 KB Output is correct
39 Correct 8 ms 35412 KB Output is correct
40 Correct 8 ms 35412 KB Output is correct
41 Correct 8 ms 35412 KB Output is correct
42 Correct 9 ms 35576 KB Output is correct
43 Correct 7 ms 35412 KB Output is correct
44 Correct 7 ms 35460 KB Output is correct
45 Correct 7 ms 35268 KB Output is correct
46 Correct 7 ms 35412 KB Output is correct
47 Correct 7 ms 35412 KB Output is correct
48 Correct 7 ms 35412 KB Output is correct
49 Correct 8 ms 35412 KB Output is correct
50 Correct 7 ms 35632 KB Output is correct
51 Correct 7 ms 35412 KB Output is correct
52 Correct 7 ms 35412 KB Output is correct
53 Correct 8 ms 35412 KB Output is correct
54 Correct 7 ms 35412 KB Output is correct
55 Correct 7 ms 35412 KB Output is correct
56 Correct 7 ms 35412 KB Output is correct
57 Correct 7 ms 35412 KB Output is correct
58 Correct 7 ms 35412 KB Output is correct
59 Correct 7 ms 35288 KB Output is correct
60 Correct 7 ms 35412 KB Output is correct
61 Correct 7 ms 35412 KB Output is correct
62 Correct 7 ms 35280 KB Output is correct
63 Correct 7 ms 35576 KB Output is correct
64 Correct 7 ms 35412 KB Output is correct

Subtask #3
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2384 KB Output is correct
2 Correct 1 ms 2384 KB Output is correct
3 Correct 1 ms 2384 KB Output is correct
4 Correct 1 ms 4432 KB Output is correct
5 Correct 1 ms 4432 KB Output is correct
6 Correct 1 ms 4432 KB Output is correct
7 Correct 1 ms 4600 KB Output is correct
8 Correct 1 ms 4436 KB Output is correct
9 Correct 1 ms 4540 KB Output is correct
10 Correct 1 ms 4436 KB Output is correct
11 Correct 1 ms 4436 KB Output is correct
12 Correct 1 ms 4436 KB Output is correct
13 Correct 1 ms 4600 KB Output is correct
14 Correct 1 ms 4436 KB Output is correct
15 Correct 1 ms 4604 KB Output is correct
16 Correct 1 ms 4436 KB Output is correct
17 Correct 1 ms 4436 KB Output is correct
18 Correct 1 ms 4436 KB Output is correct
19 Correct 1 ms 4436 KB Output is correct
20 Correct 1 ms 4436 KB Output is correct
21 Correct 1 ms 4436 KB Output is correct
22 Correct 1 ms 4436 KB Output is correct
23 Correct 1 ms 4436 KB Output is correct
24 Correct 1 ms 4436 KB Output is correct
25 Correct 1 ms 4436 KB Output is correct
26 Correct 1 ms 4600 KB Output is correct
27 Correct 1 ms 4436 KB Output is correct
28 Correct 1 ms 4436 KB Output is correct
29 Correct 1 ms 4436 KB Output is correct
30 Correct 1 ms 4436 KB Output is correct
31 Correct 1 ms 4436 KB Output is correct
32 Correct 1 ms 4436 KB Output is correct
33 Correct 1 ms 4436 KB Output is correct
34 Correct 7 ms 35412 KB Output is correct
35 Correct 7 ms 35412 KB Output is correct
36 Correct 8 ms 35412 KB Output is correct
37 Correct 8 ms 35412 KB Output is correct
38 Correct 8 ms 35580 KB Output is correct
39 Correct 8 ms 35412 KB Output is correct
40 Correct 8 ms 35412 KB Output is correct
41 Correct 8 ms 35412 KB Output is correct
42 Correct 9 ms 35576 KB Output is correct
43 Correct 7 ms 35412 KB Output is correct
44 Correct 7 ms 35460 KB Output is correct
45 Correct 7 ms 35268 KB Output is correct
46 Correct 7 ms 35412 KB Output is correct
47 Correct 7 ms 35412 KB Output is correct
48 Correct 7 ms 35412 KB Output is correct
49 Correct 8 ms 35412 KB Output is correct
50 Correct 7 ms 35632 KB Output is correct
51 Correct 7 ms 35412 KB Output is correct
52 Correct 7 ms 35412 KB Output is correct
53 Correct 8 ms 35412 KB Output is correct
54 Correct 7 ms 35412 KB Output is correct
55 Correct 7 ms 35412 KB Output is correct
56 Correct 7 ms 35412 KB Output is correct
57 Correct 7 ms 35412 KB Output is correct
58 Correct 7 ms 35412 KB Output is correct
59 Correct 7 ms 35288 KB Output is correct
60 Correct 7 ms 35412 KB Output is correct
61 Correct 7 ms 35412 KB Output is correct
62 Correct 7 ms 35280 KB Output is correct
63 Correct 7 ms 35576 KB Output is correct
64 Correct 7 ms 35412 KB Output is correct
65 Runtime error 36 ms 6476 KB Execution killed with signal 11
66 Halted 0 ms 0 KB -