#include "wiring.h"
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <map>
#include <set>
#include <assert.h>
using namespace std;
long long N,M;
vector < int > x,y;
long long DP[25][200005];
bool have2[25][200005];
set < int > have;
map < int , int > cha;
int who1[100005];
int who2[100005];
int xx=0;
long long F(long long a,long long b)
{
if(a==N&&b==M) return 0;
if(a==N||b==M||abs(who2[b]-who1[a])>10) return 1e18;
if(have2[who2[b]-who1[a]+10][a]) return DP[who2[b]-who1[a]+10][a];
have2[who2[b]-who1[a]+10][a]=1;
DP[who2[b]-who1[a]+10][a]=(long long) abs(y[b]-x[a])+min(F(a+1,b+1),min(F(a+1,b),F(a,b+1)));
return DP[who2[b]-who1[a]+10][a];
}
long long min_total_length(vector< int > r, vector < int > b)
{
long long ans=0,i,now=0;
N=r.size();
M=b.size();
x=r;
y=b;
for(auto i:r) have.insert(i);
for(auto i:b) have.insert(i);
for(auto i:have) cha[i]=now++;
for(i=0;i<N;i++) who1[i]=cha[r[i]];
for(i=0;i<M;i++) who2[i]=cha[b[i]];
if(b[0]>r[N-1])
{
if(N<=M)
{
for(i=0;i<min(N,M);i++) ans+=(long long) b[i]-r[i];
for(i=N;i<M;i++) ans+=(long long) b[i]-r[N-1];
}
else
{
for(i=1;i<=M;i++) ans+=(long long) b[M-i]-r[N-i];
for(i=0;i<N-M;i++) ans+=(long long) b[0]-r[i];
}
return ans;
}
else return F(0,0);
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
460 KB |
Output is correct |
2 |
Incorrect |
1 ms |
204 KB |
3rd lines differ - on the 1st token, expected: '14340', found: '1000000000000000000' |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
111 ms |
16772 KB |
Output is correct |
4 |
Correct |
109 ms |
16636 KB |
Output is correct |
5 |
Correct |
109 ms |
16640 KB |
Output is correct |
6 |
Correct |
147 ms |
22272 KB |
Output is correct |
7 |
Correct |
148 ms |
22208 KB |
Output is correct |
8 |
Correct |
144 ms |
22208 KB |
Output is correct |
9 |
Correct |
146 ms |
22216 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
460 KB |
Output is correct |
3 |
Correct |
204 ms |
61892 KB |
Output is correct |
4 |
Correct |
219 ms |
61824 KB |
Output is correct |
5 |
Correct |
1 ms |
460 KB |
Output is correct |
6 |
Correct |
1 ms |
460 KB |
Output is correct |
7 |
Correct |
1 ms |
460 KB |
Output is correct |
8 |
Correct |
1 ms |
460 KB |
Output is correct |
9 |
Correct |
1 ms |
440 KB |
Output is correct |
10 |
Correct |
1 ms |
460 KB |
Output is correct |
11 |
Correct |
1 ms |
440 KB |
Output is correct |
12 |
Correct |
1 ms |
460 KB |
Output is correct |
13 |
Correct |
1 ms |
460 KB |
Output is correct |
14 |
Correct |
1 ms |
432 KB |
Output is correct |
15 |
Correct |
1 ms |
588 KB |
Output is correct |
16 |
Correct |
1 ms |
588 KB |
Output is correct |
17 |
Correct |
1 ms |
588 KB |
Output is correct |
18 |
Correct |
195 ms |
62152 KB |
Output is correct |
19 |
Correct |
196 ms |
61988 KB |
Output is correct |
20 |
Correct |
200 ms |
62276 KB |
Output is correct |
21 |
Correct |
200 ms |
61972 KB |
Output is correct |
22 |
Correct |
197 ms |
62104 KB |
Output is correct |
23 |
Correct |
200 ms |
62144 KB |
Output is correct |
24 |
Correct |
192 ms |
62252 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
460 KB |
Output is correct |
2 |
Incorrect |
137 ms |
22212 KB |
3rd lines differ - on the 1st token, expected: '373710605', found: '1000000000000000000' |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
460 KB |
Output is correct |
2 |
Incorrect |
1 ms |
204 KB |
3rd lines differ - on the 1st token, expected: '14340', found: '1000000000000000000' |
3 |
Halted |
0 ms |
0 KB |
- |