#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<=500000);
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;
| ~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
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 |
2 ms |
332 KB |
Output is correct |
6 |
Correct |
1 ms |
204 KB |
Output is correct |
7 |
Correct |
30 ms |
2808 KB |
Output is correct |
8 |
Correct |
35 ms |
2756 KB |
Output is correct |
9 |
Correct |
28 ms |
2884 KB |
Output is correct |
10 |
Correct |
28 ms |
2904 KB |
Output is correct |
11 |
Correct |
29 ms |
2800 KB |
Output is correct |
12 |
Correct |
29 ms |
2876 KB |
Output is correct |
13 |
Correct |
28 ms |
2876 KB |
Output is correct |
14 |
Correct |
29 ms |
2808 KB |
Output is correct |
15 |
Correct |
29 ms |
2828 KB |
Output is correct |
16 |
Correct |
29 ms |
2772 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
115 ms |
16788 KB |
Output is correct |
4 |
Correct |
105 ms |
16628 KB |
Output is correct |
5 |
Correct |
106 ms |
16636 KB |
Output is correct |
6 |
Correct |
145 ms |
22208 KB |
Output is correct |
7 |
Correct |
143 ms |
22084 KB |
Output is correct |
8 |
Correct |
142 ms |
22112 KB |
Output is correct |
9 |
Correct |
149 ms |
22196 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
256 KB |
Output is correct |
3 |
Runtime error |
503 ms |
144452 KB |
Execution killed with signal 6 |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Incorrect |
138 ms |
22168 KB |
3rd lines differ - on the 1st token, expected: '373710605', found: '1000000000000000000' |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
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 |
2 ms |
332 KB |
Output is correct |
6 |
Correct |
1 ms |
204 KB |
Output is correct |
7 |
Correct |
30 ms |
2808 KB |
Output is correct |
8 |
Correct |
35 ms |
2756 KB |
Output is correct |
9 |
Correct |
28 ms |
2884 KB |
Output is correct |
10 |
Correct |
28 ms |
2904 KB |
Output is correct |
11 |
Correct |
29 ms |
2800 KB |
Output is correct |
12 |
Correct |
29 ms |
2876 KB |
Output is correct |
13 |
Correct |
28 ms |
2876 KB |
Output is correct |
14 |
Correct |
29 ms |
2808 KB |
Output is correct |
15 |
Correct |
29 ms |
2828 KB |
Output is correct |
16 |
Correct |
29 ms |
2772 KB |
Output is correct |
17 |
Correct |
1 ms |
204 KB |
Output is correct |
18 |
Correct |
1 ms |
332 KB |
Output is correct |
19 |
Correct |
115 ms |
16788 KB |
Output is correct |
20 |
Correct |
105 ms |
16628 KB |
Output is correct |
21 |
Correct |
106 ms |
16636 KB |
Output is correct |
22 |
Correct |
145 ms |
22208 KB |
Output is correct |
23 |
Correct |
143 ms |
22084 KB |
Output is correct |
24 |
Correct |
142 ms |
22112 KB |
Output is correct |
25 |
Correct |
149 ms |
22196 KB |
Output is correct |
26 |
Correct |
1 ms |
204 KB |
Output is correct |
27 |
Correct |
1 ms |
256 KB |
Output is correct |
28 |
Runtime error |
503 ms |
144452 KB |
Execution killed with signal 6 |
29 |
Halted |
0 ms |
0 KB |
- |