#include <bits/stdc++.h>
#define ll long long
#define db long double
#define N 200005
#define II pair <ll,ll>
#define III pair <ll,II>
#define IV pair <vector <int>,vector <int> >
#define IDB pair <db,int>
#define TII pair <treap*,treap*>
#define fst first
#define snd second
#define BIT(x,i) ((x>>i)&1)
#define pi acos(-1)
#define to_radian(x) (x*pi/180.0)
#define to_degree(x) (x*180.0/pi)
#define Log(x) (31-__builtin_clz((int)x))
#define LogLL(x) (63-__builtin_clzll((ll)x))
using namespace std;
#include "wiring.h"
II a[N];
ll f[N],n,i,j,k,Begin,sum[N],sub[N],l[N],r[N];
const ll oo=round(1e18);
ll min_total_length(vector <int> Red,vector <int> Blue)
{
for(int k:Red) a[++n]={ k,0 };
for(int k:Blue) a[++n]={ k,1 };
sort(a+1,a+n+1);
for(i=1;i<=n;i++)
{
if(i==1 || a[i].snd!=a[i-1].snd) Begin=i;
if(i==n || a[i].snd!=a[i+1].snd)
{
sum[Begin]=a[Begin].fst; l[Begin]=1;
for(j=Begin+1;j<=i;j++) sum[j]=sum[j-1]+a[j].fst,l[j]=j-Begin+1;
sub[i]=-a[i].fst; r[i]=1;
for(j=i-1;j>=Begin;j--) sub[j]=sub[j+1]-a[j].fst,r[j]=i-j+1;
}
}
for(i=1;i<=n;i++) f[i]=oo;
for(i=1;i<=n;i++)
{
if(i==1 || a[i].snd!=a[i-1].snd) Begin=i;
if(Begin>1 && (i==n || a[i].snd!=a[i+1].snd))
{
ll mi=oo;
for(j=Begin;j<=i;j++)
{
if(l[j]<=l[Begin-1])
{
k=Begin-l[j];
mi=min(mi,min(f[k],f[k-1])+sub[k]+a[Begin-1].fst*r[k]);
}
f[j]=min(f[j],mi+sum[j]-a[Begin-1].fst*l[j]);
}
mi=oo;
for(k=Begin-l[Begin-1];k<Begin;k++)
{
mi=min(mi,min(f[k],f[k-1])+sub[k]+a[Begin].fst*r[k]);
if(r[k]<=r[Begin])
{
j=Begin+r[k]-1;
f[j]=min(f[j],mi+sum[j]-a[Begin].fst*l[j]);
}
}
}
}
return f[n];
}
/*
int main()
{
freopen("wiring.inp","r",stdin);
freopen("wiring.out","w",stdout);
int n,m;
cin>>n>>m;
vector <int> r,b;
for(int i=1;i<=n;i++) cin>>k,r.push_back(k);
for(int i=1;i<=m;i++) cin>>k,b.push_back(k);
cout<<min_total_length(r,b);
}
*/
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
6488 KB |
Output is correct |
2 |
Correct |
1 ms |
6648 KB |
Output is correct |
3 |
Correct |
2 ms |
6488 KB |
Output is correct |
4 |
Correct |
2 ms |
6492 KB |
Output is correct |
5 |
Correct |
1 ms |
6488 KB |
Output is correct |
6 |
Correct |
2 ms |
6492 KB |
Output is correct |
7 |
Correct |
1 ms |
6488 KB |
Output is correct |
8 |
Correct |
2 ms |
6744 KB |
Output is correct |
9 |
Correct |
1 ms |
6488 KB |
Output is correct |
10 |
Correct |
1 ms |
6488 KB |
Output is correct |
11 |
Correct |
2 ms |
6488 KB |
Output is correct |
12 |
Correct |
1 ms |
6488 KB |
Output is correct |
13 |
Correct |
2 ms |
6492 KB |
Output is correct |
14 |
Correct |
1 ms |
6500 KB |
Output is correct |
15 |
Correct |
1 ms |
6492 KB |
Output is correct |
16 |
Correct |
1 ms |
6492 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
6488 KB |
Output is correct |
2 |
Correct |
1 ms |
6488 KB |
Output is correct |
3 |
Correct |
19 ms |
11280 KB |
Output is correct |
4 |
Correct |
19 ms |
12480 KB |
Output is correct |
5 |
Correct |
19 ms |
12624 KB |
Output is correct |
6 |
Correct |
28 ms |
14672 KB |
Output is correct |
7 |
Correct |
25 ms |
14672 KB |
Output is correct |
8 |
Correct |
25 ms |
14672 KB |
Output is correct |
9 |
Correct |
25 ms |
14680 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
6488 KB |
Output is correct |
2 |
Correct |
1 ms |
6492 KB |
Output is correct |
3 |
Correct |
36 ms |
12880 KB |
Output is correct |
4 |
Correct |
38 ms |
14420 KB |
Output is correct |
5 |
Correct |
1 ms |
6488 KB |
Output is correct |
6 |
Correct |
1 ms |
6488 KB |
Output is correct |
7 |
Correct |
2 ms |
6488 KB |
Output is correct |
8 |
Correct |
1 ms |
6492 KB |
Output is correct |
9 |
Correct |
1 ms |
6488 KB |
Output is correct |
10 |
Correct |
1 ms |
6492 KB |
Output is correct |
11 |
Correct |
2 ms |
6492 KB |
Output is correct |
12 |
Correct |
1 ms |
6492 KB |
Output is correct |
13 |
Correct |
1 ms |
6488 KB |
Output is correct |
14 |
Correct |
1 ms |
6488 KB |
Output is correct |
15 |
Correct |
1 ms |
6488 KB |
Output is correct |
16 |
Correct |
1 ms |
6488 KB |
Output is correct |
17 |
Correct |
1 ms |
6488 KB |
Output is correct |
18 |
Correct |
36 ms |
14652 KB |
Output is correct |
19 |
Correct |
37 ms |
14788 KB |
Output is correct |
20 |
Correct |
39 ms |
14640 KB |
Output is correct |
21 |
Correct |
35 ms |
14684 KB |
Output is correct |
22 |
Correct |
36 ms |
14672 KB |
Output is correct |
23 |
Correct |
36 ms |
14672 KB |
Output is correct |
24 |
Correct |
36 ms |
14656 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
6492 KB |
Output is correct |
2 |
Correct |
33 ms |
12880 KB |
Output is correct |
3 |
Correct |
33 ms |
14160 KB |
Output is correct |
4 |
Correct |
35 ms |
14012 KB |
Output is correct |
5 |
Correct |
35 ms |
14040 KB |
Output is correct |
6 |
Correct |
1 ms |
6492 KB |
Output is correct |
7 |
Correct |
1 ms |
6492 KB |
Output is correct |
8 |
Correct |
1 ms |
6488 KB |
Output is correct |
9 |
Correct |
1 ms |
6492 KB |
Output is correct |
10 |
Correct |
1 ms |
6492 KB |
Output is correct |
11 |
Correct |
1 ms |
6488 KB |
Output is correct |
12 |
Correct |
2 ms |
6488 KB |
Output is correct |
13 |
Correct |
1 ms |
6488 KB |
Output is correct |
14 |
Correct |
1 ms |
6488 KB |
Output is correct |
15 |
Correct |
1 ms |
6488 KB |
Output is correct |
16 |
Correct |
1 ms |
6488 KB |
Output is correct |
17 |
Correct |
1 ms |
6492 KB |
Output is correct |
18 |
Correct |
31 ms |
14172 KB |
Output is correct |
19 |
Correct |
32 ms |
14160 KB |
Output is correct |
20 |
Correct |
31 ms |
14360 KB |
Output is correct |
21 |
Correct |
29 ms |
14168 KB |
Output is correct |
22 |
Correct |
30 ms |
14168 KB |
Output is correct |
23 |
Correct |
27 ms |
14160 KB |
Output is correct |
24 |
Correct |
28 ms |
14416 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
6488 KB |
Output is correct |
2 |
Correct |
1 ms |
6648 KB |
Output is correct |
3 |
Correct |
2 ms |
6488 KB |
Output is correct |
4 |
Correct |
2 ms |
6492 KB |
Output is correct |
5 |
Correct |
1 ms |
6488 KB |
Output is correct |
6 |
Correct |
2 ms |
6492 KB |
Output is correct |
7 |
Correct |
1 ms |
6488 KB |
Output is correct |
8 |
Correct |
2 ms |
6744 KB |
Output is correct |
9 |
Correct |
1 ms |
6488 KB |
Output is correct |
10 |
Correct |
1 ms |
6488 KB |
Output is correct |
11 |
Correct |
2 ms |
6488 KB |
Output is correct |
12 |
Correct |
1 ms |
6488 KB |
Output is correct |
13 |
Correct |
2 ms |
6492 KB |
Output is correct |
14 |
Correct |
1 ms |
6500 KB |
Output is correct |
15 |
Correct |
1 ms |
6492 KB |
Output is correct |
16 |
Correct |
1 ms |
6492 KB |
Output is correct |
17 |
Correct |
1 ms |
6488 KB |
Output is correct |
18 |
Correct |
1 ms |
6488 KB |
Output is correct |
19 |
Correct |
19 ms |
11280 KB |
Output is correct |
20 |
Correct |
19 ms |
12480 KB |
Output is correct |
21 |
Correct |
19 ms |
12624 KB |
Output is correct |
22 |
Correct |
28 ms |
14672 KB |
Output is correct |
23 |
Correct |
25 ms |
14672 KB |
Output is correct |
24 |
Correct |
25 ms |
14672 KB |
Output is correct |
25 |
Correct |
25 ms |
14680 KB |
Output is correct |
26 |
Correct |
1 ms |
6488 KB |
Output is correct |
27 |
Correct |
1 ms |
6492 KB |
Output is correct |
28 |
Correct |
36 ms |
12880 KB |
Output is correct |
29 |
Correct |
38 ms |
14420 KB |
Output is correct |
30 |
Correct |
1 ms |
6488 KB |
Output is correct |
31 |
Correct |
1 ms |
6488 KB |
Output is correct |
32 |
Correct |
2 ms |
6488 KB |
Output is correct |
33 |
Correct |
1 ms |
6492 KB |
Output is correct |
34 |
Correct |
1 ms |
6488 KB |
Output is correct |
35 |
Correct |
1 ms |
6492 KB |
Output is correct |
36 |
Correct |
2 ms |
6492 KB |
Output is correct |
37 |
Correct |
1 ms |
6492 KB |
Output is correct |
38 |
Correct |
1 ms |
6488 KB |
Output is correct |
39 |
Correct |
1 ms |
6488 KB |
Output is correct |
40 |
Correct |
1 ms |
6488 KB |
Output is correct |
41 |
Correct |
1 ms |
6488 KB |
Output is correct |
42 |
Correct |
1 ms |
6488 KB |
Output is correct |
43 |
Correct |
36 ms |
14652 KB |
Output is correct |
44 |
Correct |
37 ms |
14788 KB |
Output is correct |
45 |
Correct |
39 ms |
14640 KB |
Output is correct |
46 |
Correct |
35 ms |
14684 KB |
Output is correct |
47 |
Correct |
36 ms |
14672 KB |
Output is correct |
48 |
Correct |
36 ms |
14672 KB |
Output is correct |
49 |
Correct |
36 ms |
14656 KB |
Output is correct |
50 |
Correct |
1 ms |
6492 KB |
Output is correct |
51 |
Correct |
33 ms |
12880 KB |
Output is correct |
52 |
Correct |
33 ms |
14160 KB |
Output is correct |
53 |
Correct |
35 ms |
14012 KB |
Output is correct |
54 |
Correct |
35 ms |
14040 KB |
Output is correct |
55 |
Correct |
1 ms |
6492 KB |
Output is correct |
56 |
Correct |
1 ms |
6492 KB |
Output is correct |
57 |
Correct |
1 ms |
6488 KB |
Output is correct |
58 |
Correct |
1 ms |
6492 KB |
Output is correct |
59 |
Correct |
1 ms |
6492 KB |
Output is correct |
60 |
Correct |
1 ms |
6488 KB |
Output is correct |
61 |
Correct |
2 ms |
6488 KB |
Output is correct |
62 |
Correct |
1 ms |
6488 KB |
Output is correct |
63 |
Correct |
1 ms |
6488 KB |
Output is correct |
64 |
Correct |
1 ms |
6488 KB |
Output is correct |
65 |
Correct |
1 ms |
6488 KB |
Output is correct |
66 |
Correct |
1 ms |
6492 KB |
Output is correct |
67 |
Correct |
31 ms |
14172 KB |
Output is correct |
68 |
Correct |
32 ms |
14160 KB |
Output is correct |
69 |
Correct |
31 ms |
14360 KB |
Output is correct |
70 |
Correct |
29 ms |
14168 KB |
Output is correct |
71 |
Correct |
30 ms |
14168 KB |
Output is correct |
72 |
Correct |
27 ms |
14160 KB |
Output is correct |
73 |
Correct |
28 ms |
14416 KB |
Output is correct |
74 |
Correct |
28 ms |
14680 KB |
Output is correct |
75 |
Correct |
34 ms |
14344 KB |
Output is correct |
76 |
Correct |
32 ms |
14880 KB |
Output is correct |
77 |
Correct |
32 ms |
14160 KB |
Output is correct |
78 |
Correct |
29 ms |
14164 KB |
Output is correct |
79 |
Correct |
32 ms |
14160 KB |
Output is correct |
80 |
Correct |
28 ms |
14160 KB |
Output is correct |
81 |
Correct |
30 ms |
14144 KB |
Output is correct |
82 |
Correct |
28 ms |
14160 KB |
Output is correct |
83 |
Correct |
26 ms |
14416 KB |
Output is correct |
84 |
Correct |
26 ms |
14676 KB |
Output is correct |
85 |
Correct |
37 ms |
14676 KB |
Output is correct |
86 |
Correct |
27 ms |
14780 KB |
Output is correct |
87 |
Correct |
30 ms |
14684 KB |
Output is correct |
88 |
Correct |
32 ms |
14712 KB |
Output is correct |
89 |
Correct |
29 ms |
14932 KB |
Output is correct |
90 |
Correct |
35 ms |
14672 KB |
Output is correct |
91 |
Correct |
30 ms |
14672 KB |
Output is correct |
92 |
Correct |
31 ms |
14672 KB |
Output is correct |
93 |
Correct |
28 ms |
14676 KB |
Output is correct |
94 |
Correct |
31 ms |
14672 KB |
Output is correct |
95 |
Correct |
31 ms |
14672 KB |
Output is correct |
96 |
Correct |
28 ms |
14784 KB |
Output is correct |
97 |
Correct |
27 ms |
14668 KB |
Output is correct |
98 |
Correct |
30 ms |
14656 KB |
Output is correct |
99 |
Correct |
29 ms |
14676 KB |
Output is correct |
100 |
Correct |
35 ms |
14668 KB |
Output is correct |
101 |
Correct |
29 ms |
14672 KB |
Output is correct |
102 |
Correct |
33 ms |
14672 KB |
Output is correct |