#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];
long long 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||(N>200||M>200)&&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;
xx++;
assert(xx<=5000000);
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);
}
Compilation message
wiring.cpp: In function 'long long int F(long long int, long long int)':
wiring.cpp:23:34: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
23 | if(a==N||b==M||(N>200||M>200)&&abs(who2[b]-who1[a])>10) return 1e18;
| ~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
588 KB |
3rd lines differ - on the 1st token, expected: '25859', found: '12752' |
2 |
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 |
113 ms |
16688 KB |
Output is correct |
4 |
Correct |
109 ms |
16668 KB |
Output is correct |
5 |
Correct |
132 ms |
16688 KB |
Output is correct |
6 |
Correct |
148 ms |
22128 KB |
Output is correct |
7 |
Correct |
149 ms |
22112 KB |
Output is correct |
8 |
Correct |
156 ms |
22156 KB |
Output is correct |
9 |
Correct |
149 ms |
22204 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Runtime error |
7 ms |
760 KB |
Execution killed with signal 11 |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
5 ms |
620 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
588 KB |
3rd lines differ - on the 1st token, expected: '25859', found: '12752' |
2 |
Halted |
0 ms |
0 KB |
- |