#include "wiring.h"
#include <bits/stdc++.h>
using namespace std;
long long N, M, A[200009], B[200009], SA[200009], SB[200009], dp[1400009];
vector<pair<int, int>> G, G2, X[100009], Y[100009], R[200009];
vector<pair<int, long long>> Z[1400009];
void prints() {
cout << "--- Data of Z ---" << endl;
for (int i = 0; i < G.size(); i++) {
for (int j = 0; j < Z[i].size(); j++) {
cout << i << " -> " << Z[i][j].first << ", Weight = " << Z[i][j].second << endl;
}
}
cout << endl;
}
void printg() {
cout << "--- Data of G ---" << endl;
for (int i = 0; i < G.size(); i++) printf("#% 3d: (% 3d, % 3d)\n", i, G[i].first, G[i].second);
cout << endl;
}
long long solve() {
for (int i = 0; i < N; i++) SA[i + 1] = SA[i] + A[i];
for (int i = 0; i < M; i++) SB[i + 1] = SB[i] + B[i];
// 調和点の追加
for (int i = 0; i < N; i++) {
int pos1 = lower_bound(A, A + N, A[i] + 1) - A;
int pos2 = lower_bound(B, B + M, A[i] + 1) - B;
G.push_back(make_pair(pos1, pos2));
for (int j = 0; j <= 1; j++) { for (int k = -1; k <= 1; k++) { G.push_back(make_pair(i + j, pos2 + k)); } }
}
for (int i = 0; i < M; i++) {
int pos1 = lower_bound(A, A + N, B[i] + 1) - A;
int pos2 = lower_bound(B, B + M, B[i] + 1) - B;
G.push_back(make_pair(pos1, pos2));
for (int j = 0; j <= 1; j++) { for (int k = -1; k <= 1; k++) { G.push_back(make_pair(pos1 + k, i + j)); } }
}
G.push_back(make_pair(0, 0));
G.push_back(make_pair(N, M));
for (int i = 0; i < G.size(); i++) {
if (G[i].first < 0 || G[i].second < 0 || G[i].first > N || G[i].second > M) continue;
if ((G[i].first == 0 || G[i].second == 0) && G[i].first + G[i].second != 0) continue;
G2.push_back(G[i]);
}
G = G2;
sort(G.begin(), G.end());
G.erase(unique(G.begin(), G.end()), G.end());
//printg();
for (int i = 0; i < G.size(); i++) {
X[G[i].first].push_back(make_pair(G[i].second, i));
Y[G[i].second].push_back(make_pair(G[i].first, i));
R[G[i].first - G[i].second + M].push_back(make_pair(G[i].first, i));
}
for (int i = 0; i <= N; i++) {
for (int j = 0; j < (int)X[i].size() - 1; j++) {
if (X[i][j + 1].first - X[i][j].first != 1) continue;
Z[X[i][j].second].push_back(make_pair(X[i][j + 1].second, abs(A[i - 1] - B[X[i][j + 1].first - 1])));
}
}
//prints();
for (int i = 0; i <= M; i++) {
for (int j = 0; j < (int)Y[i].size() - 1; j++) {
if (Y[i][j + 1].first - Y[i][j].first != 1) continue;
Z[Y[i][j].second].push_back(make_pair(Y[i][j + 1].second, abs(B[i - 1] - A[Y[i][j + 1].first - 1])));
}
}
//prints();
for (int i = -M; i <= N; i++) {
for (int j = 0; j < (int)R[i + M].size() - 1; j++) {
int cx = i + M;
long long B1 = SA[R[cx][j + 1].first] - SA[R[cx][j].first];
long long B2 = SB[R[cx][j + 1].first - i] - SB[R[cx][j].first - i];
Z[R[cx][j].second].push_back(make_pair(R[cx][j + 1].second, abs(B1 - B2)));
}
}
//prints();
for (int i = 0; i < (int)G.size(); i++) dp[i] = (1LL << 60);
dp[0] = 0;
for (int i = 0; i < (int)G.size(); i++) {
for (int j = 0; j < (int)Z[i].size(); j++) dp[Z[i][j].first] = min(dp[Z[i][j].first], dp[i] + Z[i][j].second);
}
return dp[G.size() - 1];
}
long long min_total_length(vector<int> r, vector<int> b) {
N = r.size(); M = b.size();
for (int i = 0; i < N; i++) A[i] = r[i];
for (int i = 0; i < M; i++) B[i] = b[i];
return solve();
}
Compilation message
wiring.cpp: In function 'void prints()':
wiring.cpp:11:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < G.size(); i++) {
~~^~~~~~~~~~
wiring.cpp:12:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j = 0; j < Z[i].size(); j++) {
~~^~~~~~~~~~~~~
wiring.cpp: In function 'void printg()':
wiring.cpp:21:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < G.size(); i++) printf("#% 3d: (% 3d, % 3d)\n", i, G[i].first, G[i].second);
~~^~~~~~~~~~
wiring.cpp: In function 'long long int solve()':
wiring.cpp:45:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < G.size(); i++) {
~~^~~~~~~~~~
wiring.cpp:56:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < G.size(); i++) {
~~^~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
36 ms |
42620 KB |
Output is correct |
2 |
Correct |
36 ms |
42624 KB |
Output is correct |
3 |
Correct |
36 ms |
42616 KB |
Output is correct |
4 |
Correct |
38 ms |
42668 KB |
Output is correct |
5 |
Correct |
38 ms |
42616 KB |
Output is correct |
6 |
Correct |
36 ms |
42596 KB |
Output is correct |
7 |
Correct |
38 ms |
42752 KB |
Output is correct |
8 |
Correct |
38 ms |
42744 KB |
Output is correct |
9 |
Correct |
37 ms |
42872 KB |
Output is correct |
10 |
Correct |
37 ms |
42880 KB |
Output is correct |
11 |
Correct |
37 ms |
42744 KB |
Output is correct |
12 |
Correct |
38 ms |
42876 KB |
Output is correct |
13 |
Correct |
37 ms |
42844 KB |
Output is correct |
14 |
Correct |
39 ms |
42852 KB |
Output is correct |
15 |
Correct |
39 ms |
42852 KB |
Output is correct |
16 |
Correct |
40 ms |
42752 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
39 ms |
42616 KB |
Output is correct |
2 |
Correct |
38 ms |
42744 KB |
Output is correct |
3 |
Correct |
196 ms |
80676 KB |
Output is correct |
4 |
Correct |
177 ms |
80756 KB |
Output is correct |
5 |
Correct |
223 ms |
86964 KB |
Output is correct |
6 |
Correct |
243 ms |
98624 KB |
Output is correct |
7 |
Correct |
250 ms |
98596 KB |
Output is correct |
8 |
Correct |
241 ms |
98588 KB |
Output is correct |
9 |
Correct |
254 ms |
98496 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
37 ms |
42624 KB |
Output is correct |
2 |
Correct |
39 ms |
42616 KB |
Output is correct |
3 |
Correct |
598 ms |
134436 KB |
Output is correct |
4 |
Correct |
664 ms |
138912 KB |
Output is correct |
5 |
Correct |
39 ms |
42616 KB |
Output is correct |
6 |
Correct |
41 ms |
42624 KB |
Output is correct |
7 |
Correct |
46 ms |
42616 KB |
Output is correct |
8 |
Correct |
38 ms |
42624 KB |
Output is correct |
9 |
Correct |
37 ms |
42616 KB |
Output is correct |
10 |
Correct |
43 ms |
42744 KB |
Output is correct |
11 |
Correct |
43 ms |
42616 KB |
Output is correct |
12 |
Correct |
38 ms |
42616 KB |
Output is correct |
13 |
Correct |
43 ms |
42708 KB |
Output is correct |
14 |
Correct |
38 ms |
42748 KB |
Output is correct |
15 |
Correct |
42 ms |
42744 KB |
Output is correct |
16 |
Correct |
39 ms |
42744 KB |
Output is correct |
17 |
Correct |
39 ms |
42756 KB |
Output is correct |
18 |
Correct |
625 ms |
136096 KB |
Output is correct |
19 |
Correct |
629 ms |
136180 KB |
Output is correct |
20 |
Correct |
650 ms |
139296 KB |
Output is correct |
21 |
Correct |
576 ms |
135840 KB |
Output is correct |
22 |
Correct |
625 ms |
136740 KB |
Output is correct |
23 |
Correct |
595 ms |
137032 KB |
Output is correct |
24 |
Correct |
602 ms |
136796 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
37 ms |
42620 KB |
Output is correct |
2 |
Correct |
488 ms |
137632 KB |
Output is correct |
3 |
Correct |
617 ms |
142156 KB |
Output is correct |
4 |
Correct |
555 ms |
142112 KB |
Output is correct |
5 |
Correct |
624 ms |
142244 KB |
Output is correct |
6 |
Correct |
40 ms |
42616 KB |
Output is correct |
7 |
Correct |
40 ms |
42624 KB |
Output is correct |
8 |
Correct |
37 ms |
42616 KB |
Output is correct |
9 |
Correct |
37 ms |
42744 KB |
Output is correct |
10 |
Correct |
39 ms |
42760 KB |
Output is correct |
11 |
Correct |
39 ms |
42744 KB |
Output is correct |
12 |
Correct |
38 ms |
42588 KB |
Output is correct |
13 |
Correct |
37 ms |
42616 KB |
Output is correct |
14 |
Correct |
37 ms |
42616 KB |
Output is correct |
15 |
Correct |
37 ms |
42744 KB |
Output is correct |
16 |
Correct |
37 ms |
42716 KB |
Output is correct |
17 |
Correct |
37 ms |
42744 KB |
Output is correct |
18 |
Correct |
417 ms |
127420 KB |
Output is correct |
19 |
Correct |
640 ms |
142820 KB |
Output is correct |
20 |
Correct |
560 ms |
142536 KB |
Output is correct |
21 |
Correct |
527 ms |
138784 KB |
Output is correct |
22 |
Correct |
364 ms |
124064 KB |
Output is correct |
23 |
Correct |
269 ms |
110388 KB |
Output is correct |
24 |
Correct |
323 ms |
118976 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
36 ms |
42620 KB |
Output is correct |
2 |
Correct |
36 ms |
42624 KB |
Output is correct |
3 |
Correct |
36 ms |
42616 KB |
Output is correct |
4 |
Correct |
38 ms |
42668 KB |
Output is correct |
5 |
Correct |
38 ms |
42616 KB |
Output is correct |
6 |
Correct |
36 ms |
42596 KB |
Output is correct |
7 |
Correct |
38 ms |
42752 KB |
Output is correct |
8 |
Correct |
38 ms |
42744 KB |
Output is correct |
9 |
Correct |
37 ms |
42872 KB |
Output is correct |
10 |
Correct |
37 ms |
42880 KB |
Output is correct |
11 |
Correct |
37 ms |
42744 KB |
Output is correct |
12 |
Correct |
38 ms |
42876 KB |
Output is correct |
13 |
Correct |
37 ms |
42844 KB |
Output is correct |
14 |
Correct |
39 ms |
42852 KB |
Output is correct |
15 |
Correct |
39 ms |
42852 KB |
Output is correct |
16 |
Correct |
40 ms |
42752 KB |
Output is correct |
17 |
Correct |
39 ms |
42616 KB |
Output is correct |
18 |
Correct |
38 ms |
42744 KB |
Output is correct |
19 |
Correct |
196 ms |
80676 KB |
Output is correct |
20 |
Correct |
177 ms |
80756 KB |
Output is correct |
21 |
Correct |
223 ms |
86964 KB |
Output is correct |
22 |
Correct |
243 ms |
98624 KB |
Output is correct |
23 |
Correct |
250 ms |
98596 KB |
Output is correct |
24 |
Correct |
241 ms |
98588 KB |
Output is correct |
25 |
Correct |
254 ms |
98496 KB |
Output is correct |
26 |
Correct |
37 ms |
42624 KB |
Output is correct |
27 |
Correct |
39 ms |
42616 KB |
Output is correct |
28 |
Correct |
598 ms |
134436 KB |
Output is correct |
29 |
Correct |
664 ms |
138912 KB |
Output is correct |
30 |
Correct |
39 ms |
42616 KB |
Output is correct |
31 |
Correct |
41 ms |
42624 KB |
Output is correct |
32 |
Correct |
46 ms |
42616 KB |
Output is correct |
33 |
Correct |
38 ms |
42624 KB |
Output is correct |
34 |
Correct |
37 ms |
42616 KB |
Output is correct |
35 |
Correct |
43 ms |
42744 KB |
Output is correct |
36 |
Correct |
43 ms |
42616 KB |
Output is correct |
37 |
Correct |
38 ms |
42616 KB |
Output is correct |
38 |
Correct |
43 ms |
42708 KB |
Output is correct |
39 |
Correct |
38 ms |
42748 KB |
Output is correct |
40 |
Correct |
42 ms |
42744 KB |
Output is correct |
41 |
Correct |
39 ms |
42744 KB |
Output is correct |
42 |
Correct |
39 ms |
42756 KB |
Output is correct |
43 |
Correct |
625 ms |
136096 KB |
Output is correct |
44 |
Correct |
629 ms |
136180 KB |
Output is correct |
45 |
Correct |
650 ms |
139296 KB |
Output is correct |
46 |
Correct |
576 ms |
135840 KB |
Output is correct |
47 |
Correct |
625 ms |
136740 KB |
Output is correct |
48 |
Correct |
595 ms |
137032 KB |
Output is correct |
49 |
Correct |
602 ms |
136796 KB |
Output is correct |
50 |
Correct |
37 ms |
42620 KB |
Output is correct |
51 |
Correct |
488 ms |
137632 KB |
Output is correct |
52 |
Correct |
617 ms |
142156 KB |
Output is correct |
53 |
Correct |
555 ms |
142112 KB |
Output is correct |
54 |
Correct |
624 ms |
142244 KB |
Output is correct |
55 |
Correct |
40 ms |
42616 KB |
Output is correct |
56 |
Correct |
40 ms |
42624 KB |
Output is correct |
57 |
Correct |
37 ms |
42616 KB |
Output is correct |
58 |
Correct |
37 ms |
42744 KB |
Output is correct |
59 |
Correct |
39 ms |
42760 KB |
Output is correct |
60 |
Correct |
39 ms |
42744 KB |
Output is correct |
61 |
Correct |
38 ms |
42588 KB |
Output is correct |
62 |
Correct |
37 ms |
42616 KB |
Output is correct |
63 |
Correct |
37 ms |
42616 KB |
Output is correct |
64 |
Correct |
37 ms |
42744 KB |
Output is correct |
65 |
Correct |
37 ms |
42716 KB |
Output is correct |
66 |
Correct |
37 ms |
42744 KB |
Output is correct |
67 |
Correct |
417 ms |
127420 KB |
Output is correct |
68 |
Correct |
640 ms |
142820 KB |
Output is correct |
69 |
Correct |
560 ms |
142536 KB |
Output is correct |
70 |
Correct |
527 ms |
138784 KB |
Output is correct |
71 |
Correct |
364 ms |
124064 KB |
Output is correct |
72 |
Correct |
269 ms |
110388 KB |
Output is correct |
73 |
Correct |
323 ms |
118976 KB |
Output is correct |
74 |
Correct |
350 ms |
121512 KB |
Output is correct |
75 |
Correct |
409 ms |
129700 KB |
Output is correct |
76 |
Correct |
368 ms |
126112 KB |
Output is correct |
77 |
Correct |
439 ms |
135328 KB |
Output is correct |
78 |
Correct |
368 ms |
126184 KB |
Output is correct |
79 |
Correct |
461 ms |
138528 KB |
Output is correct |
80 |
Correct |
357 ms |
125016 KB |
Output is correct |
81 |
Correct |
310 ms |
119872 KB |
Output is correct |
82 |
Correct |
284 ms |
113600 KB |
Output is correct |
83 |
Correct |
295 ms |
110912 KB |
Output is correct |
84 |
Correct |
274 ms |
108356 KB |
Output is correct |
85 |
Correct |
492 ms |
132876 KB |
Output is correct |
86 |
Correct |
331 ms |
121408 KB |
Output is correct |
87 |
Correct |
302 ms |
115948 KB |
Output is correct |
88 |
Correct |
382 ms |
128388 KB |
Output is correct |
89 |
Correct |
401 ms |
128800 KB |
Output is correct |
90 |
Correct |
404 ms |
132132 KB |
Output is correct |
91 |
Correct |
308 ms |
117440 KB |
Output is correct |
92 |
Correct |
441 ms |
133152 KB |
Output is correct |
93 |
Correct |
396 ms |
125008 KB |
Output is correct |
94 |
Correct |
441 ms |
134960 KB |
Output is correct |
95 |
Correct |
529 ms |
136864 KB |
Output is correct |
96 |
Correct |
324 ms |
116288 KB |
Output is correct |
97 |
Correct |
311 ms |
116544 KB |
Output is correct |
98 |
Correct |
341 ms |
120624 KB |
Output is correct |
99 |
Correct |
333 ms |
120636 KB |
Output is correct |
100 |
Correct |
474 ms |
140192 KB |
Output is correct |
101 |
Correct |
369 ms |
121836 KB |
Output is correct |
102 |
Correct |
358 ms |
125248 KB |
Output is correct |