#include <bits/stdc++.h>
/*
DP flowers
*/
int main(){
int n,m;
std::cin>>n>>m;
std::vector<int> sprinklers;
std::vector<int> flowers;
std::map<int,int> flowerinds;
for(int i=0;i<n;i++){
int x;
std::cin>>x;
sprinklers.push_back(x);
}
for(int i=0;i<m;i++){
int x;
std::cin>>x;
flowers.push_back(x);
flowerinds[x]=i;
}
flowerinds[2000000000]=m;
int lower=0,upper=1000000002;
while(1){
int kval=(lower+upper)/2-1;
if(lower+1>=upper){
if(lower==1000000001){
std::cout<<"-1\n";
return 0;
}else{
kval=lower;
}
}
std::vector<std::pair<int,int>> dp(n+1);
for(int i=0;i<n;i++){
std::pair<int,int> curval=dp[i];
dp[i+1]=std::max(dp[i+1],{curval.first,0});//do nothing
if(curval.first<m){
if(flowers[curval.first]>=sprinklers[i]-kval){
dp[i+1]=std::max(dp[i+1],{flowerinds.upper_bound(sprinklers[i])->second,-1});//left
}
if(flowers[curval.first]>=sprinklers[i]){
dp[i+1]=std::max(dp[i+1],{flowerinds.upper_bound(sprinklers[i]+kval)->second,1});//right
}
if(i+1<n&&sprinklers[i]<=sprinklers[i]+kval){//RL (no holes)
if(flowers[curval.first]>=sprinklers[i+1]-kval){
dp[i+2]=std::max(dp[i+2],{flowerinds.upper_bound(sprinklers[i]+kval)->second,2});
}
}
}
}
if(lower+1>=upper){
std::cout<<lower<<'\n';
std::string rec(n,' ');
int ind=n;
while(ind){
if(dp[ind].second==-1){
rec[ind-1]='L';
ind--;
}else if(dp[ind].second==1){
rec[ind-1]='R';
ind--;
}else if(dp[ind].second==2){//RL
rec[ind-1]='L';
rec[ind-2]='R';
ind-=2;
}else{//don't care ("do nothing")
rec[ind-1]='L';
ind--;
}
}
std::cout<<rec<<'\n';
return 0;
}
if(dp.back().first==m){
upper=kval+1;
}else{
lower=kval+1;
}
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Correct |
2 |
Correct |
0 ms |
344 KB |
Correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Correct |
2 |
Correct |
29 ms |
4452 KB |
Correct |
3 |
Correct |
0 ms |
348 KB |
Correct |
4 |
Correct |
32 ms |
6452 KB |
Correct |
5 |
Correct |
33 ms |
6348 KB |
Correct |
6 |
Correct |
0 ms |
344 KB |
Correct |
7 |
Correct |
0 ms |
436 KB |
Correct |
8 |
Correct |
6 ms |
1552 KB |
Correct |
9 |
Correct |
0 ms |
440 KB |
Correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Correct |
2 |
Correct |
35 ms |
4836 KB |
Correct |
3 |
Correct |
18 ms |
856 KB |
Correct |
4 |
Correct |
300 ms |
8632 KB |
Correct |
5 |
Correct |
298 ms |
8724 KB |
Correct |
6 |
Correct |
0 ms |
348 KB |
Correct |
7 |
Correct |
0 ms |
348 KB |
Correct |
8 |
Correct |
53 ms |
5264 KB |
Correct |
9 |
Correct |
58 ms |
5548 KB |
Correct |
10 |
Correct |
409 ms |
7648 KB |
Correct |
11 |
Correct |
60 ms |
2744 KB |
Correct |
12 |
Correct |
154 ms |
6600 KB |
Correct |
13 |
Correct |
199 ms |
5820 KB |
Correct |
14 |
Correct |
187 ms |
6452 KB |
Correct |
15 |
Correct |
233 ms |
6600 KB |
Correct |
16 |
Correct |
158 ms |
5048 KB |
Correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Correct |
2 |
Correct |
0 ms |
344 KB |
Correct |
3 |
Correct |
1 ms |
344 KB |
Correct |
4 |
Correct |
1 ms |
344 KB |
Correct |
5 |
Correct |
1 ms |
348 KB |
Correct |
6 |
Correct |
0 ms |
348 KB |
Correct |
7 |
Correct |
0 ms |
348 KB |
Correct |
8 |
Correct |
0 ms |
348 KB |
Correct |
9 |
Correct |
0 ms |
348 KB |
Correct |
10 |
Correct |
0 ms |
424 KB |
Correct |
11 |
Correct |
0 ms |
348 KB |
Correct |
12 |
Correct |
1 ms |
600 KB |
Correct |
13 |
Correct |
0 ms |
344 KB |
Correct |
14 |
Correct |
0 ms |
348 KB |
Correct |
15 |
Correct |
0 ms |
348 KB |
Correct |
16 |
Correct |
1 ms |
440 KB |
Correct |
17 |
Correct |
1 ms |
344 KB |
Correct |
18 |
Correct |
0 ms |
392 KB |
Correct |
19 |
Correct |
0 ms |
348 KB |
Correct |
20 |
Correct |
1 ms |
348 KB |
Correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Correct |
2 |
Correct |
70 ms |
4956 KB |
Correct |
3 |
Correct |
318 ms |
8428 KB |
Correct |
4 |
Correct |
316 ms |
8648 KB |
Correct |
5 |
Correct |
309 ms |
8232 KB |
Correct |
6 |
Correct |
318 ms |
8320 KB |
Correct |
7 |
Correct |
307 ms |
8364 KB |
Correct |
8 |
Correct |
327 ms |
8468 KB |
Correct |
9 |
Correct |
336 ms |
8392 KB |
Correct |
10 |
Correct |
324 ms |
8308 KB |
Correct |
11 |
Correct |
322 ms |
8544 KB |
Correct |
12 |
Correct |
0 ms |
348 KB |
Correct |
13 |
Correct |
0 ms |
348 KB |
Correct |
14 |
Correct |
65 ms |
2704 KB |
Correct |
15 |
Correct |
86 ms |
2744 KB |
Correct |
16 |
Correct |
85 ms |
2632 KB |
Correct |
17 |
Correct |
35 ms |
2648 KB |
Correct |
18 |
Correct |
50 ms |
2896 KB |
Correct |
19 |
Correct |
96 ms |
3616 KB |
Correct |
20 |
Correct |
257 ms |
8120 KB |
Correct |
21 |
Correct |
274 ms |
7940 KB |
Correct |
22 |
Correct |
245 ms |
7496 KB |
Correct |
23 |
Correct |
254 ms |
7604 KB |
Correct |
24 |
Correct |
186 ms |
6008 KB |
Correct |
25 |
Correct |
191 ms |
6112 KB |
Correct |
26 |
Correct |
115 ms |
2640 KB |
Correct |
27 |
Correct |
110 ms |
2996 KB |
Correct |
28 |
Correct |
209 ms |
5856 KB |
Correct |
29 |
Correct |
173 ms |
5236 KB |
Correct |
30 |
Correct |
188 ms |
5576 KB |
Correct |
31 |
Correct |
232 ms |
7760 KB |
Correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Correct |
2 |
Correct |
0 ms |
344 KB |
Correct |
3 |
Correct |
29 ms |
4452 KB |
Correct |
4 |
Correct |
0 ms |
348 KB |
Correct |
5 |
Correct |
32 ms |
6452 KB |
Correct |
6 |
Correct |
33 ms |
6348 KB |
Correct |
7 |
Correct |
0 ms |
344 KB |
Correct |
8 |
Correct |
0 ms |
436 KB |
Correct |
9 |
Correct |
6 ms |
1552 KB |
Correct |
10 |
Correct |
0 ms |
440 KB |
Correct |
11 |
Correct |
35 ms |
4836 KB |
Correct |
12 |
Correct |
18 ms |
856 KB |
Correct |
13 |
Correct |
300 ms |
8632 KB |
Correct |
14 |
Correct |
298 ms |
8724 KB |
Correct |
15 |
Correct |
0 ms |
348 KB |
Correct |
16 |
Correct |
0 ms |
348 KB |
Correct |
17 |
Correct |
53 ms |
5264 KB |
Correct |
18 |
Correct |
58 ms |
5548 KB |
Correct |
19 |
Correct |
409 ms |
7648 KB |
Correct |
20 |
Correct |
60 ms |
2744 KB |
Correct |
21 |
Correct |
154 ms |
6600 KB |
Correct |
22 |
Correct |
199 ms |
5820 KB |
Correct |
23 |
Correct |
187 ms |
6452 KB |
Correct |
24 |
Correct |
233 ms |
6600 KB |
Correct |
25 |
Correct |
158 ms |
5048 KB |
Correct |
26 |
Correct |
1 ms |
344 KB |
Correct |
27 |
Correct |
1 ms |
344 KB |
Correct |
28 |
Correct |
1 ms |
348 KB |
Correct |
29 |
Correct |
0 ms |
348 KB |
Correct |
30 |
Correct |
0 ms |
348 KB |
Correct |
31 |
Correct |
0 ms |
348 KB |
Correct |
32 |
Correct |
0 ms |
348 KB |
Correct |
33 |
Correct |
0 ms |
424 KB |
Correct |
34 |
Correct |
0 ms |
348 KB |
Correct |
35 |
Correct |
1 ms |
600 KB |
Correct |
36 |
Correct |
0 ms |
344 KB |
Correct |
37 |
Correct |
0 ms |
348 KB |
Correct |
38 |
Correct |
0 ms |
348 KB |
Correct |
39 |
Correct |
1 ms |
440 KB |
Correct |
40 |
Correct |
1 ms |
344 KB |
Correct |
41 |
Correct |
0 ms |
392 KB |
Correct |
42 |
Correct |
0 ms |
348 KB |
Correct |
43 |
Correct |
1 ms |
348 KB |
Correct |
44 |
Correct |
70 ms |
4956 KB |
Correct |
45 |
Correct |
318 ms |
8428 KB |
Correct |
46 |
Correct |
316 ms |
8648 KB |
Correct |
47 |
Correct |
309 ms |
8232 KB |
Correct |
48 |
Correct |
318 ms |
8320 KB |
Correct |
49 |
Correct |
307 ms |
8364 KB |
Correct |
50 |
Correct |
327 ms |
8468 KB |
Correct |
51 |
Correct |
336 ms |
8392 KB |
Correct |
52 |
Correct |
324 ms |
8308 KB |
Correct |
53 |
Correct |
322 ms |
8544 KB |
Correct |
54 |
Correct |
0 ms |
348 KB |
Correct |
55 |
Correct |
0 ms |
348 KB |
Correct |
56 |
Correct |
65 ms |
2704 KB |
Correct |
57 |
Correct |
86 ms |
2744 KB |
Correct |
58 |
Correct |
85 ms |
2632 KB |
Correct |
59 |
Correct |
35 ms |
2648 KB |
Correct |
60 |
Correct |
50 ms |
2896 KB |
Correct |
61 |
Correct |
96 ms |
3616 KB |
Correct |
62 |
Correct |
257 ms |
8120 KB |
Correct |
63 |
Correct |
274 ms |
7940 KB |
Correct |
64 |
Correct |
245 ms |
7496 KB |
Correct |
65 |
Correct |
254 ms |
7604 KB |
Correct |
66 |
Correct |
186 ms |
6008 KB |
Correct |
67 |
Correct |
191 ms |
6112 KB |
Correct |
68 |
Correct |
115 ms |
2640 KB |
Correct |
69 |
Correct |
110 ms |
2996 KB |
Correct |
70 |
Correct |
209 ms |
5856 KB |
Correct |
71 |
Correct |
173 ms |
5236 KB |
Correct |
72 |
Correct |
188 ms |
5576 KB |
Correct |
73 |
Correct |
232 ms |
7760 KB |
Correct |
74 |
Correct |
42 ms |
5332 KB |
Correct |
75 |
Correct |
301 ms |
8636 KB |
Correct |
76 |
Correct |
344 ms |
8596 KB |
Correct |
77 |
Correct |
0 ms |
348 KB |
Correct |
78 |
Correct |
59 ms |
5252 KB |
Correct |
79 |
Correct |
343 ms |
5560 KB |
Correct |
80 |
Correct |
62 ms |
7608 KB |
Correct |
81 |
Correct |
71 ms |
2712 KB |
Correct |
82 |
Correct |
85 ms |
2728 KB |
Correct |
83 |
Correct |
81 ms |
2640 KB |
Correct |
84 |
Correct |
42 ms |
3800 KB |
Correct |
85 |
Correct |
215 ms |
6428 KB |
Correct |
86 |
Correct |
266 ms |
6568 KB |
Correct |
87 |
Correct |
234 ms |
7764 KB |
Correct |
88 |
Correct |
32 ms |
6356 KB |
Correct |
89 |
Correct |
32 ms |
6420 KB |
Correct |