1408D - Searchlights
Let's define as xx our move to the right and as yy our move to the up. For all pairs (i,j)(i,j) of (robber, searchlight) at least one of this should be true: x+ai>cj, y+bi>dj. So if x≤cj−ai then y≥dj−bi+1.
Let's make an array rr of length C=1e6 and write on each position of xx the minimum value of yy. For each (i,j)(i,j) we should make rx=max(rx,dj−bi+1) for all x≤cj−ai. So we have nm queries of max on prefix. We can do it using suffix maximums. After we will calculate all ax the answer is minx(x+rx).
1 #include<iostream>
2 #include<algorithm>
3 #include<cstring>
4 #include<cmath>
5 using namespace std;
6 const int N = 2e3 + 10;
7 int n, m;
8 int a[N], b[N];
9 int c[N], d[N];
10 int ans = 10000000;
11 int t[1000010];//t[x]当选择向右移动x时，至少需要向上移动t[x]个单位
12
13 int main(){
14 scanf("%d%d",&n,&m);
15 for(int i = 1 ; i <= n ; i++){
16 scanf("%d%d",&a[i],&b[i]);
17 }//匪徒
18 for(int i = 1 ; i <= m ; i++){
19 scanf("%d%d",&c[i],&d[i]);
20 }//灯
21 for(int i = 1 ; i <= n ; i++){
22 for(int j = 1 ; j <= m ; j++){
23 if(a[i] <= c[j] && b[i] <= d[j]){
24 t[c[j] - a[i]] = max(t[c[j] - a[i]], d[j] - b[i] + 1);
25 }
26 }
27 }
28
29 for(int i = 1000000 ; i >= 0 ; i--){
30 t[i] = max(t[i], t[i + 1]);
31 ans = min(ans, t[i] + i);
32 }
33 printf("%d
",ans);
34
35 return 0;
36 }
干