# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
792684 |
2023-07-25T08:04:54 Z |
Kaitokid |
Wiring (IOI17_wiring) |
C++14 |
|
55 ms |
16332 KB |
//#include "wiring.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll min_total_length(vector<int> r, vector<int> b) {
int n=r.size()+b.size();
vector<pair<ll,ll> > g;
g.push_back({-1,-1});
for(int i=0;i<r.size();i++)g.push_back({r[i],0});
for(int i=0;i<b.size();i++)g.push_back({b[i],1});
sort(g.begin(),g.end());
vector<ll>dp(n+1),pr(n+1),lst(3*n,-1),nx(n+1);
vector<ll>prv={-1,-1};
for(int i=n;i>=1;i--)
{
nx[i]=prv[1-g[i].second];
prv[g[i].second]=i;
}
prv={-1,-1};
ll s=0;
lst[n]=0;
for(int i=1;i<=n;i++)
{
dp[i]=10000000000000000;
pr[i]=pr[i-1]+(2*g[i].second-1)*g[i].first;
s+=2*g[i].second-1;
if(nx[i]!=-1)
dp[i]=dp[i-1]+g[nx[i]].first-g[i].first;
prv[g[i].second]=i;
if(prv[1-g[i].second]!=-1)
{
dp[i]=min(dp[i],dp[i-1]+g[i].first-g[prv[1-g[i].second]].first);
if(lst[n+s]!=-1)
{
dp[i]=min(dp[i],dp[lst[n+s]]+abs(pr[i]-pr[lst[s+n]]));
}
}
//cout<<dp[i]<<" ";
lst[n+s]=i;
}
//cout<<endl;
return dp[n];
}
/*int main()
{
cout<<min_total_length({0,1,2,3}, {4,5,6,7});
}
*/
Compilation message
wiring.cpp: In function 'll min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:9:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
9 | for(int i=0;i<r.size();i++)g.push_back({r[i],0});
| ~^~~~~~~~~
wiring.cpp:10:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
10 | for(int i=0;i<b.size();i++)g.push_back({b[i],1});
| ~^~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
1 ms |
300 KB |
Output is correct |
11 |
Correct |
0 ms |
212 KB |
Output is correct |
12 |
Correct |
1 ms |
212 KB |
Output is correct |
13 |
Correct |
1 ms |
300 KB |
Output is correct |
14 |
Correct |
1 ms |
300 KB |
Output is correct |
15 |
Correct |
1 ms |
212 KB |
Output is correct |
16 |
Correct |
0 ms |
300 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
22 ms |
12240 KB |
Output is correct |
4 |
Correct |
22 ms |
12244 KB |
Output is correct |
5 |
Correct |
22 ms |
12224 KB |
Output is correct |
6 |
Correct |
29 ms |
16312 KB |
Output is correct |
7 |
Correct |
31 ms |
16284 KB |
Output is correct |
8 |
Correct |
30 ms |
16284 KB |
Output is correct |
9 |
Correct |
29 ms |
16280 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
45 ms |
16268 KB |
Output is correct |
4 |
Correct |
42 ms |
15940 KB |
Output is correct |
5 |
Correct |
0 ms |
292 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
0 ms |
212 KB |
Output is correct |
9 |
Correct |
0 ms |
212 KB |
Output is correct |
10 |
Correct |
0 ms |
304 KB |
Output is correct |
11 |
Correct |
1 ms |
296 KB |
Output is correct |
12 |
Correct |
0 ms |
212 KB |
Output is correct |
13 |
Correct |
0 ms |
212 KB |
Output is correct |
14 |
Correct |
0 ms |
212 KB |
Output is correct |
15 |
Correct |
1 ms |
212 KB |
Output is correct |
16 |
Correct |
0 ms |
304 KB |
Output is correct |
17 |
Correct |
0 ms |
212 KB |
Output is correct |
18 |
Correct |
39 ms |
16272 KB |
Output is correct |
19 |
Correct |
39 ms |
16264 KB |
Output is correct |
20 |
Correct |
43 ms |
16280 KB |
Output is correct |
21 |
Correct |
40 ms |
16180 KB |
Output is correct |
22 |
Correct |
40 ms |
16288 KB |
Output is correct |
23 |
Correct |
40 ms |
16312 KB |
Output is correct |
24 |
Correct |
40 ms |
16276 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
31 ms |
15612 KB |
Output is correct |
3 |
Correct |
35 ms |
15640 KB |
Output is correct |
4 |
Correct |
32 ms |
15548 KB |
Output is correct |
5 |
Correct |
37 ms |
15632 KB |
Output is correct |
6 |
Correct |
1 ms |
296 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
304 KB |
Output is correct |
10 |
Correct |
1 ms |
212 KB |
Output is correct |
11 |
Correct |
1 ms |
256 KB |
Output is correct |
12 |
Correct |
0 ms |
212 KB |
Output is correct |
13 |
Correct |
1 ms |
212 KB |
Output is correct |
14 |
Correct |
1 ms |
212 KB |
Output is correct |
15 |
Correct |
1 ms |
212 KB |
Output is correct |
16 |
Correct |
1 ms |
212 KB |
Output is correct |
17 |
Correct |
1 ms |
212 KB |
Output is correct |
18 |
Correct |
32 ms |
15612 KB |
Output is correct |
19 |
Correct |
33 ms |
15604 KB |
Output is correct |
20 |
Correct |
33 ms |
15544 KB |
Output is correct |
21 |
Correct |
37 ms |
15644 KB |
Output is correct |
22 |
Correct |
31 ms |
15544 KB |
Output is correct |
23 |
Correct |
34 ms |
15640 KB |
Output is correct |
24 |
Correct |
38 ms |
15652 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
1 ms |
300 KB |
Output is correct |
11 |
Correct |
0 ms |
212 KB |
Output is correct |
12 |
Correct |
1 ms |
212 KB |
Output is correct |
13 |
Correct |
1 ms |
300 KB |
Output is correct |
14 |
Correct |
1 ms |
300 KB |
Output is correct |
15 |
Correct |
1 ms |
212 KB |
Output is correct |
16 |
Correct |
0 ms |
300 KB |
Output is correct |
17 |
Correct |
1 ms |
212 KB |
Output is correct |
18 |
Correct |
1 ms |
212 KB |
Output is correct |
19 |
Correct |
22 ms |
12240 KB |
Output is correct |
20 |
Correct |
22 ms |
12244 KB |
Output is correct |
21 |
Correct |
22 ms |
12224 KB |
Output is correct |
22 |
Correct |
29 ms |
16312 KB |
Output is correct |
23 |
Correct |
31 ms |
16284 KB |
Output is correct |
24 |
Correct |
30 ms |
16284 KB |
Output is correct |
25 |
Correct |
29 ms |
16280 KB |
Output is correct |
26 |
Correct |
0 ms |
212 KB |
Output is correct |
27 |
Correct |
0 ms |
212 KB |
Output is correct |
28 |
Correct |
45 ms |
16268 KB |
Output is correct |
29 |
Correct |
42 ms |
15940 KB |
Output is correct |
30 |
Correct |
0 ms |
292 KB |
Output is correct |
31 |
Correct |
1 ms |
212 KB |
Output is correct |
32 |
Correct |
0 ms |
212 KB |
Output is correct |
33 |
Correct |
0 ms |
212 KB |
Output is correct |
34 |
Correct |
0 ms |
212 KB |
Output is correct |
35 |
Correct |
0 ms |
304 KB |
Output is correct |
36 |
Correct |
1 ms |
296 KB |
Output is correct |
37 |
Correct |
0 ms |
212 KB |
Output is correct |
38 |
Correct |
0 ms |
212 KB |
Output is correct |
39 |
Correct |
0 ms |
212 KB |
Output is correct |
40 |
Correct |
1 ms |
212 KB |
Output is correct |
41 |
Correct |
0 ms |
304 KB |
Output is correct |
42 |
Correct |
0 ms |
212 KB |
Output is correct |
43 |
Correct |
39 ms |
16272 KB |
Output is correct |
44 |
Correct |
39 ms |
16264 KB |
Output is correct |
45 |
Correct |
43 ms |
16280 KB |
Output is correct |
46 |
Correct |
40 ms |
16180 KB |
Output is correct |
47 |
Correct |
40 ms |
16288 KB |
Output is correct |
48 |
Correct |
40 ms |
16312 KB |
Output is correct |
49 |
Correct |
40 ms |
16276 KB |
Output is correct |
50 |
Correct |
1 ms |
212 KB |
Output is correct |
51 |
Correct |
31 ms |
15612 KB |
Output is correct |
52 |
Correct |
35 ms |
15640 KB |
Output is correct |
53 |
Correct |
32 ms |
15548 KB |
Output is correct |
54 |
Correct |
37 ms |
15632 KB |
Output is correct |
55 |
Correct |
1 ms |
296 KB |
Output is correct |
56 |
Correct |
1 ms |
212 KB |
Output is correct |
57 |
Correct |
1 ms |
212 KB |
Output is correct |
58 |
Correct |
1 ms |
304 KB |
Output is correct |
59 |
Correct |
1 ms |
212 KB |
Output is correct |
60 |
Correct |
1 ms |
256 KB |
Output is correct |
61 |
Correct |
0 ms |
212 KB |
Output is correct |
62 |
Correct |
1 ms |
212 KB |
Output is correct |
63 |
Correct |
1 ms |
212 KB |
Output is correct |
64 |
Correct |
1 ms |
212 KB |
Output is correct |
65 |
Correct |
1 ms |
212 KB |
Output is correct |
66 |
Correct |
1 ms |
212 KB |
Output is correct |
67 |
Correct |
32 ms |
15612 KB |
Output is correct |
68 |
Correct |
33 ms |
15604 KB |
Output is correct |
69 |
Correct |
33 ms |
15544 KB |
Output is correct |
70 |
Correct |
37 ms |
15644 KB |
Output is correct |
71 |
Correct |
31 ms |
15544 KB |
Output is correct |
72 |
Correct |
34 ms |
15640 KB |
Output is correct |
73 |
Correct |
38 ms |
15652 KB |
Output is correct |
74 |
Correct |
47 ms |
16252 KB |
Output is correct |
75 |
Correct |
33 ms |
15904 KB |
Output is correct |
76 |
Correct |
30 ms |
16280 KB |
Output is correct |
77 |
Correct |
33 ms |
15676 KB |
Output is correct |
78 |
Correct |
48 ms |
15684 KB |
Output is correct |
79 |
Correct |
34 ms |
15628 KB |
Output is correct |
80 |
Correct |
31 ms |
15636 KB |
Output is correct |
81 |
Correct |
34 ms |
15800 KB |
Output is correct |
82 |
Correct |
46 ms |
15744 KB |
Output is correct |
83 |
Correct |
31 ms |
15928 KB |
Output is correct |
84 |
Correct |
34 ms |
16284 KB |
Output is correct |
85 |
Correct |
49 ms |
16224 KB |
Output is correct |
86 |
Correct |
42 ms |
16276 KB |
Output is correct |
87 |
Correct |
37 ms |
16288 KB |
Output is correct |
88 |
Correct |
37 ms |
16272 KB |
Output is correct |
89 |
Correct |
41 ms |
16280 KB |
Output is correct |
90 |
Correct |
55 ms |
16232 KB |
Output is correct |
91 |
Correct |
39 ms |
16280 KB |
Output is correct |
92 |
Correct |
46 ms |
16292 KB |
Output is correct |
93 |
Correct |
39 ms |
16332 KB |
Output is correct |
94 |
Correct |
42 ms |
16264 KB |
Output is correct |
95 |
Correct |
35 ms |
16276 KB |
Output is correct |
96 |
Correct |
32 ms |
16264 KB |
Output is correct |
97 |
Correct |
38 ms |
16284 KB |
Output is correct |
98 |
Correct |
36 ms |
16284 KB |
Output is correct |
99 |
Correct |
47 ms |
16248 KB |
Output is correct |
100 |
Correct |
38 ms |
16240 KB |
Output is correct |
101 |
Correct |
39 ms |
16220 KB |
Output is correct |
102 |
Correct |
33 ms |
16268 KB |
Output is correct |