# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
975146 |
2024-05-04T13:36:28 Z |
LucaIlie |
Wiring (IOI17_wiring) |
C++17 |
|
54 ms |
44272 KB |
#include "wiring.h"
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 4e5;
const long long INF = 1e15;
struct wire {
int c, x;
};
struct segment {
int l, r;
};
long long sp[MAX_N + 1];
wire wires[MAX_N + 1];
vector<segment> seg;
vector<long long> dp[MAX_N + 1], minPref[MAX_N + 1], minSuf[MAX_N + 1];
long long sum( int l, int r ) {
return sp[r] - sp[l - 1];
}
long long min_total_length( vector<int> a, vector<int> b ) {
#define int long long
int n = a.size() + b.size();
for ( int i = 0; i < a.size(); i++ )
wires[i + 1] = { 0, a[i] };
for ( int i = 0; i < b.size(); i++ )
wires[i + 1 + a.size()] = { 1, b[i] };
sort( wires + 1, wires + 1 + n, []( wire x, wire y ) {
return x.x < y.x;
} );
for ( int i = 1; i <= n; i++ )
sp[i] = sp[i - 1] + wires[i].x;
int i = 1;
while ( i <= n ) {
int j = i;
while ( j + 1 <= n && wires[i].c == wires[j + 1].c )
j++;
seg.push_back( { i, j } );
i = j + 1;
}
for ( int i = 0; i < seg.size(); i++ ) {
dp[i].resize( seg[i].r - seg[i].l + 2 );
minPref[i].resize( seg[i].r - seg[i].l + 2 );
minSuf[i].resize( seg[i].r - seg[i].l + 2 );
}
for ( int x = 1; x <= seg[0].r - seg[0].l + 1; x++ )
dp[0][x] = INF;
for ( int i = 1; i < seg.size(); i++ ) {
for ( int x = 0; x < dp[i - 1].size(); x++ ) {
int z = seg[i - 1].r - seg[i - 1].l + 1 - x;
minPref[i - 1][z] = dp[i - 1][x] - sum( seg[i - 1].l + x, seg[i - 1].r ) + z * wires[seg[i - 1].r].x;
minSuf[i - 1][z] = dp[i - 1][x] - sum( seg[i - 1].l + x, seg[i - 1].r ) + z * wires[seg[i].l].x;
}
for ( int x = dp[i - 1].size() - 2; x >= 0; x-- )
minSuf[i - 1][x] = min( minSuf[i - 1][x], minSuf[i - 1][x + 1] );
for ( int x = 1; x < dp[i - 1].size(); x++ )
minPref[i - 1][x] = min( minPref[i - 1][x], minPref[i - 1][x - 1] );
for ( int x = 0; x < dp[i].size(); x++ ) {
dp[i][x] = min( (x == 0 ? INF : minPref[i - 1][min( x, (int)dp[i - 1].size()) - 1] - wires[seg[i - 1].r].x * x),
(x >= dp[i - 1].size() ? INF : minSuf[i - 1][x] ) - wires[seg[i].l].x * x )
+ sum( seg[i].l, seg[i].l + x - 1 );
}
}
return dp[seg.size() - 1].back();
}
Compilation message
wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:30:24: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
30 | for ( int i = 0; i < a.size(); i++ )
| ~~^~~~~~~~~~
wiring.cpp:32:24: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
32 | for ( int i = 0; i < b.size(); i++ )
| ~~^~~~~~~~~~
wiring.cpp:45:26: warning: narrowing conversion of 'i' from 'long long int' to 'int' [-Wnarrowing]
45 | seg.push_back( { i, j } );
| ^
wiring.cpp:45:29: warning: narrowing conversion of 'j' from 'long long int' to 'int' [-Wnarrowing]
45 | seg.push_back( { i, j } );
| ^
wiring.cpp:49:24: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<segment>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
49 | for ( int i = 0; i < seg.size(); i++ ) {
| ~~^~~~~~~~~~~~
wiring.cpp:57:24: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<segment>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
57 | for ( int i = 1; i < seg.size(); i++ ) {
| ~~^~~~~~~~~~~~
wiring.cpp:58:28: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
58 | for ( int x = 0; x < dp[i - 1].size(); x++ ) {
| ~~^~~~~~~~~~~~~~~~~~
wiring.cpp:66:28: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
66 | for ( int x = 1; x < dp[i - 1].size(); x++ )
| ~~^~~~~~~~~~~~~~~~~~
wiring.cpp:69:28: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
69 | for ( int x = 0; x < dp[i].size(); x++ ) {
| ~~^~~~~~~~~~~~~~
wiring.cpp:71:32: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
71 | (x >= dp[i - 1].size() ? INF : minSuf[i - 1][x] ) - wires[seg[i].l].x * x )
| ~~^~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
29276 KB |
Output is correct |
2 |
Correct |
7 ms |
29120 KB |
Output is correct |
3 |
Correct |
6 ms |
29272 KB |
Output is correct |
4 |
Correct |
7 ms |
29276 KB |
Output is correct |
5 |
Correct |
7 ms |
29528 KB |
Output is correct |
6 |
Correct |
8 ms |
29344 KB |
Output is correct |
7 |
Correct |
7 ms |
29276 KB |
Output is correct |
8 |
Correct |
7 ms |
29276 KB |
Output is correct |
9 |
Correct |
7 ms |
29276 KB |
Output is correct |
10 |
Correct |
7 ms |
29276 KB |
Output is correct |
11 |
Correct |
7 ms |
29276 KB |
Output is correct |
12 |
Correct |
7 ms |
29276 KB |
Output is correct |
13 |
Correct |
7 ms |
29276 KB |
Output is correct |
14 |
Correct |
7 ms |
29272 KB |
Output is correct |
15 |
Correct |
7 ms |
29276 KB |
Output is correct |
16 |
Correct |
8 ms |
29276 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
29276 KB |
Output is correct |
2 |
Correct |
7 ms |
29276 KB |
Output is correct |
3 |
Correct |
27 ms |
38224 KB |
Output is correct |
4 |
Correct |
26 ms |
38744 KB |
Output is correct |
5 |
Correct |
26 ms |
38548 KB |
Output is correct |
6 |
Correct |
40 ms |
41044 KB |
Output is correct |
7 |
Correct |
37 ms |
41040 KB |
Output is correct |
8 |
Correct |
31 ms |
41048 KB |
Output is correct |
9 |
Correct |
32 ms |
41048 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
29276 KB |
Output is correct |
2 |
Correct |
6 ms |
29276 KB |
Output is correct |
3 |
Correct |
54 ms |
44060 KB |
Output is correct |
4 |
Correct |
48 ms |
41888 KB |
Output is correct |
5 |
Correct |
7 ms |
29272 KB |
Output is correct |
6 |
Correct |
7 ms |
29272 KB |
Output is correct |
7 |
Correct |
6 ms |
29276 KB |
Output is correct |
8 |
Correct |
7 ms |
29272 KB |
Output is correct |
9 |
Correct |
7 ms |
29276 KB |
Output is correct |
10 |
Correct |
7 ms |
29140 KB |
Output is correct |
11 |
Correct |
8 ms |
29276 KB |
Output is correct |
12 |
Correct |
7 ms |
29276 KB |
Output is correct |
13 |
Correct |
8 ms |
29276 KB |
Output is correct |
14 |
Correct |
7 ms |
29276 KB |
Output is correct |
15 |
Correct |
7 ms |
29276 KB |
Output is correct |
16 |
Correct |
7 ms |
29376 KB |
Output is correct |
17 |
Correct |
7 ms |
29272 KB |
Output is correct |
18 |
Correct |
53 ms |
44272 KB |
Output is correct |
19 |
Correct |
50 ms |
44036 KB |
Output is correct |
20 |
Correct |
49 ms |
42188 KB |
Output is correct |
21 |
Correct |
52 ms |
44208 KB |
Output is correct |
22 |
Correct |
53 ms |
43452 KB |
Output is correct |
23 |
Correct |
52 ms |
43464 KB |
Output is correct |
24 |
Correct |
48 ms |
43464 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
29276 KB |
Output is correct |
2 |
Correct |
38 ms |
39860 KB |
Output is correct |
3 |
Correct |
44 ms |
41676 KB |
Output is correct |
4 |
Correct |
40 ms |
40276 KB |
Output is correct |
5 |
Correct |
45 ms |
41504 KB |
Output is correct |
6 |
Correct |
7 ms |
29344 KB |
Output is correct |
7 |
Correct |
7 ms |
29272 KB |
Output is correct |
8 |
Correct |
7 ms |
29276 KB |
Output is correct |
9 |
Correct |
6 ms |
29332 KB |
Output is correct |
10 |
Correct |
7 ms |
29276 KB |
Output is correct |
11 |
Correct |
7 ms |
29276 KB |
Output is correct |
12 |
Correct |
7 ms |
29276 KB |
Output is correct |
13 |
Correct |
7 ms |
29276 KB |
Output is correct |
14 |
Correct |
7 ms |
29276 KB |
Output is correct |
15 |
Correct |
7 ms |
29276 KB |
Output is correct |
16 |
Correct |
7 ms |
29276 KB |
Output is correct |
17 |
Correct |
7 ms |
29340 KB |
Output is correct |
18 |
Correct |
38 ms |
40488 KB |
Output is correct |
19 |
Correct |
43 ms |
40536 KB |
Output is correct |
20 |
Correct |
37 ms |
40352 KB |
Output is correct |
21 |
Correct |
35 ms |
40352 KB |
Output is correct |
22 |
Correct |
36 ms |
40492 KB |
Output is correct |
23 |
Correct |
32 ms |
40276 KB |
Output is correct |
24 |
Correct |
32 ms |
40484 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
29276 KB |
Output is correct |
2 |
Correct |
7 ms |
29120 KB |
Output is correct |
3 |
Correct |
6 ms |
29272 KB |
Output is correct |
4 |
Correct |
7 ms |
29276 KB |
Output is correct |
5 |
Correct |
7 ms |
29528 KB |
Output is correct |
6 |
Correct |
8 ms |
29344 KB |
Output is correct |
7 |
Correct |
7 ms |
29276 KB |
Output is correct |
8 |
Correct |
7 ms |
29276 KB |
Output is correct |
9 |
Correct |
7 ms |
29276 KB |
Output is correct |
10 |
Correct |
7 ms |
29276 KB |
Output is correct |
11 |
Correct |
7 ms |
29276 KB |
Output is correct |
12 |
Correct |
7 ms |
29276 KB |
Output is correct |
13 |
Correct |
7 ms |
29276 KB |
Output is correct |
14 |
Correct |
7 ms |
29272 KB |
Output is correct |
15 |
Correct |
7 ms |
29276 KB |
Output is correct |
16 |
Correct |
8 ms |
29276 KB |
Output is correct |
17 |
Correct |
7 ms |
29276 KB |
Output is correct |
18 |
Correct |
7 ms |
29276 KB |
Output is correct |
19 |
Correct |
27 ms |
38224 KB |
Output is correct |
20 |
Correct |
26 ms |
38744 KB |
Output is correct |
21 |
Correct |
26 ms |
38548 KB |
Output is correct |
22 |
Correct |
40 ms |
41044 KB |
Output is correct |
23 |
Correct |
37 ms |
41040 KB |
Output is correct |
24 |
Correct |
31 ms |
41048 KB |
Output is correct |
25 |
Correct |
32 ms |
41048 KB |
Output is correct |
26 |
Correct |
7 ms |
29276 KB |
Output is correct |
27 |
Correct |
6 ms |
29276 KB |
Output is correct |
28 |
Correct |
54 ms |
44060 KB |
Output is correct |
29 |
Correct |
48 ms |
41888 KB |
Output is correct |
30 |
Correct |
7 ms |
29272 KB |
Output is correct |
31 |
Correct |
7 ms |
29272 KB |
Output is correct |
32 |
Correct |
6 ms |
29276 KB |
Output is correct |
33 |
Correct |
7 ms |
29272 KB |
Output is correct |
34 |
Correct |
7 ms |
29276 KB |
Output is correct |
35 |
Correct |
7 ms |
29140 KB |
Output is correct |
36 |
Correct |
8 ms |
29276 KB |
Output is correct |
37 |
Correct |
7 ms |
29276 KB |
Output is correct |
38 |
Correct |
8 ms |
29276 KB |
Output is correct |
39 |
Correct |
7 ms |
29276 KB |
Output is correct |
40 |
Correct |
7 ms |
29276 KB |
Output is correct |
41 |
Correct |
7 ms |
29376 KB |
Output is correct |
42 |
Correct |
7 ms |
29272 KB |
Output is correct |
43 |
Correct |
53 ms |
44272 KB |
Output is correct |
44 |
Correct |
50 ms |
44036 KB |
Output is correct |
45 |
Correct |
49 ms |
42188 KB |
Output is correct |
46 |
Correct |
52 ms |
44208 KB |
Output is correct |
47 |
Correct |
53 ms |
43452 KB |
Output is correct |
48 |
Correct |
52 ms |
43464 KB |
Output is correct |
49 |
Correct |
48 ms |
43464 KB |
Output is correct |
50 |
Correct |
6 ms |
29276 KB |
Output is correct |
51 |
Correct |
38 ms |
39860 KB |
Output is correct |
52 |
Correct |
44 ms |
41676 KB |
Output is correct |
53 |
Correct |
40 ms |
40276 KB |
Output is correct |
54 |
Correct |
45 ms |
41504 KB |
Output is correct |
55 |
Correct |
7 ms |
29344 KB |
Output is correct |
56 |
Correct |
7 ms |
29272 KB |
Output is correct |
57 |
Correct |
7 ms |
29276 KB |
Output is correct |
58 |
Correct |
6 ms |
29332 KB |
Output is correct |
59 |
Correct |
7 ms |
29276 KB |
Output is correct |
60 |
Correct |
7 ms |
29276 KB |
Output is correct |
61 |
Correct |
7 ms |
29276 KB |
Output is correct |
62 |
Correct |
7 ms |
29276 KB |
Output is correct |
63 |
Correct |
7 ms |
29276 KB |
Output is correct |
64 |
Correct |
7 ms |
29276 KB |
Output is correct |
65 |
Correct |
7 ms |
29276 KB |
Output is correct |
66 |
Correct |
7 ms |
29340 KB |
Output is correct |
67 |
Correct |
38 ms |
40488 KB |
Output is correct |
68 |
Correct |
43 ms |
40536 KB |
Output is correct |
69 |
Correct |
37 ms |
40352 KB |
Output is correct |
70 |
Correct |
35 ms |
40352 KB |
Output is correct |
71 |
Correct |
36 ms |
40492 KB |
Output is correct |
72 |
Correct |
32 ms |
40276 KB |
Output is correct |
73 |
Correct |
32 ms |
40484 KB |
Output is correct |
74 |
Correct |
33 ms |
41048 KB |
Output is correct |
75 |
Correct |
39 ms |
40828 KB |
Output is correct |
76 |
Correct |
37 ms |
41036 KB |
Output is correct |
77 |
Correct |
37 ms |
40528 KB |
Output is correct |
78 |
Correct |
38 ms |
40348 KB |
Output is correct |
79 |
Correct |
37 ms |
40360 KB |
Output is correct |
80 |
Correct |
32 ms |
40532 KB |
Output is correct |
81 |
Correct |
36 ms |
40532 KB |
Output is correct |
82 |
Correct |
31 ms |
40528 KB |
Output is correct |
83 |
Correct |
31 ms |
40796 KB |
Output is correct |
84 |
Correct |
32 ms |
41040 KB |
Output is correct |
85 |
Correct |
38 ms |
41040 KB |
Output is correct |
86 |
Correct |
34 ms |
41040 KB |
Output is correct |
87 |
Correct |
34 ms |
41108 KB |
Output is correct |
88 |
Correct |
36 ms |
41180 KB |
Output is correct |
89 |
Correct |
34 ms |
41148 KB |
Output is correct |
90 |
Correct |
42 ms |
41048 KB |
Output is correct |
91 |
Correct |
33 ms |
41124 KB |
Output is correct |
92 |
Correct |
36 ms |
41044 KB |
Output is correct |
93 |
Correct |
34 ms |
41044 KB |
Output is correct |
94 |
Correct |
36 ms |
41120 KB |
Output is correct |
95 |
Correct |
42 ms |
41036 KB |
Output is correct |
96 |
Correct |
40 ms |
41108 KB |
Output is correct |
97 |
Correct |
33 ms |
41052 KB |
Output is correct |
98 |
Correct |
36 ms |
41144 KB |
Output is correct |
99 |
Correct |
36 ms |
41052 KB |
Output is correct |
100 |
Correct |
43 ms |
41116 KB |
Output is correct |
101 |
Correct |
35 ms |
41044 KB |
Output is correct |
102 |
Correct |
41 ms |
41120 KB |
Output is correct |