#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;
map < pair < int , int > , int > DP;
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(DP.find(make_pair(a,b))!=DP.end()) return DP[make_pair(a,b)];
xx++;
assert(xx<=5000000);
DP[make_pair(a,b)]=(long long) abs(y[b]-x[a])+min(F(a+1,b+1),min(F(a+1,b),F(a,b+1)));
return DP[make_pair(a,b)];
}
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:22:34: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
22 | if(a==N||b==M||(N>200||M>200)&&abs(who2[b]-who1[a])>=10) return 1e18;
| ~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
# |
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 |
1 ms |
332 KB |
Output is correct |
4 |
Correct |
1 ms |
332 KB |
Output is correct |
5 |
Correct |
1 ms |
332 KB |
Output is correct |
6 |
Correct |
1 ms |
204 KB |
Output is correct |
7 |
Correct |
28 ms |
2852 KB |
Output is correct |
8 |
Correct |
35 ms |
2868 KB |
Output is correct |
9 |
Correct |
31 ms |
2892 KB |
Output is correct |
10 |
Correct |
29 ms |
2836 KB |
Output is correct |
11 |
Correct |
29 ms |
2844 KB |
Output is correct |
12 |
Correct |
28 ms |
2868 KB |
Output is correct |
13 |
Correct |
29 ms |
2908 KB |
Output is correct |
14 |
Correct |
29 ms |
2784 KB |
Output is correct |
15 |
Correct |
29 ms |
2768 KB |
Output is correct |
16 |
Correct |
28 ms |
2884 KB |
Output is correct |
# |
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 |
112 ms |
16752 KB |
Output is correct |
4 |
Correct |
107 ms |
17112 KB |
Output is correct |
5 |
Correct |
106 ms |
17020 KB |
Output is correct |
6 |
Correct |
142 ms |
22500 KB |
Output is correct |
7 |
Correct |
149 ms |
22704 KB |
Output is correct |
8 |
Correct |
141 ms |
22520 KB |
Output is correct |
9 |
Correct |
145 ms |
22596 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
769 ms |
104020 KB |
Output is correct |
4 |
Execution timed out |
1051 ms |
106228 KB |
Time limit exceeded |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Incorrect |
140 ms |
22244 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 |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
1 ms |
332 KB |
Output is correct |
4 |
Correct |
1 ms |
332 KB |
Output is correct |
5 |
Correct |
1 ms |
332 KB |
Output is correct |
6 |
Correct |
1 ms |
204 KB |
Output is correct |
7 |
Correct |
28 ms |
2852 KB |
Output is correct |
8 |
Correct |
35 ms |
2868 KB |
Output is correct |
9 |
Correct |
31 ms |
2892 KB |
Output is correct |
10 |
Correct |
29 ms |
2836 KB |
Output is correct |
11 |
Correct |
29 ms |
2844 KB |
Output is correct |
12 |
Correct |
28 ms |
2868 KB |
Output is correct |
13 |
Correct |
29 ms |
2908 KB |
Output is correct |
14 |
Correct |
29 ms |
2784 KB |
Output is correct |
15 |
Correct |
29 ms |
2768 KB |
Output is correct |
16 |
Correct |
28 ms |
2884 KB |
Output is correct |
17 |
Correct |
1 ms |
204 KB |
Output is correct |
18 |
Correct |
1 ms |
332 KB |
Output is correct |
19 |
Correct |
112 ms |
16752 KB |
Output is correct |
20 |
Correct |
107 ms |
17112 KB |
Output is correct |
21 |
Correct |
106 ms |
17020 KB |
Output is correct |
22 |
Correct |
142 ms |
22500 KB |
Output is correct |
23 |
Correct |
149 ms |
22704 KB |
Output is correct |
24 |
Correct |
141 ms |
22520 KB |
Output is correct |
25 |
Correct |
145 ms |
22596 KB |
Output is correct |
26 |
Correct |
1 ms |
204 KB |
Output is correct |
27 |
Correct |
1 ms |
204 KB |
Output is correct |
28 |
Correct |
769 ms |
104020 KB |
Output is correct |
29 |
Execution timed out |
1051 ms |
106228 KB |
Time limit exceeded |
30 |
Halted |
0 ms |
0 KB |
- |