#include <bits/stdc++.h>
using namespace std ;
const int MAX = 2004 ;
int a[MAX] , b[MAX] ;
int n , m , q ;
int dp[MAX][MAX][2] ;
int solve(int i , int j , bool flag)
{
if(i < 1 || i > n || j < 1 || j > m)
return 0 ;
int &ret = dp[i][j][flag] ;
if(ret != -1)
return ret ;
ret = 0 ;
if(a[i] > b[j] || flag)
{
int j2 = j+1 ;
while(j2 <= m && b[j2] < a[i])
++j2 ;
if(j2 == m+1)
ret = max(ret , m-j) ;
else
ret = max(ret , solve(i , j2 , 0) + j2-j) ;
j2 = j-1 ;
while(j2 >= 1 && b[j2] < a[i])
--j2 ;
if(!j2)
ret = max(ret , j-1) ;
else
ret = max(ret , solve(i , j2 , 0) + j-j2) ;
}
if(a[i] < b[j] || flag)
{
int i2 = i+1 ;
while(i2 <= n && a[i2] < b[j])
++i2 ;
if(i2 == n+1)
ret = max(ret , n-i) ;
else
ret = max(ret , solve(i2 , j , 0) + i2-i) ;
i2 = i-1 ;
while(i2 >= 1 && a[i2] < b[j])
--i2 ;
if(!i2)
ret = max(ret , i-1) ;
else
ret = max(ret , solve(i2 , j , 0) + i-i2) ;
}
return ret ;
}
int main()
{
memset(dp , -1 , sizeof(dp)) ;
ios_base::sync_with_stdio(0) ;
cin.tie(0) ;
cin>>n>>m>>q ;
for(int i = 1 ; i <= n ; ++i)
cin>>a[i] ;
for(int i = 1 ; i <= m ; ++i)
cin>>b[i] ;
while(q--)
{
int i , j ;
cin>>i>>j ;
cout<<solve(i , j , 1)<<"\n" ;
}
return 0 ;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
11 ms |
31700 KB |
Output is correct |
2 |
Correct |
13 ms |
31664 KB |
Output is correct |
3 |
Correct |
11 ms |
31760 KB |
Output is correct |
4 |
Correct |
13 ms |
31648 KB |
Output is correct |
5 |
Correct |
11 ms |
31700 KB |
Output is correct |
6 |
Correct |
12 ms |
31700 KB |
Output is correct |
7 |
Correct |
12 ms |
31756 KB |
Output is correct |
8 |
Correct |
12 ms |
31700 KB |
Output is correct |
9 |
Correct |
11 ms |
31764 KB |
Output is correct |
10 |
Correct |
13 ms |
31760 KB |
Output is correct |
11 |
Correct |
12 ms |
31700 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
11 ms |
31700 KB |
Output is correct |
2 |
Correct |
13 ms |
31664 KB |
Output is correct |
3 |
Correct |
11 ms |
31760 KB |
Output is correct |
4 |
Correct |
13 ms |
31648 KB |
Output is correct |
5 |
Correct |
11 ms |
31700 KB |
Output is correct |
6 |
Correct |
12 ms |
31700 KB |
Output is correct |
7 |
Correct |
12 ms |
31756 KB |
Output is correct |
8 |
Correct |
12 ms |
31700 KB |
Output is correct |
9 |
Correct |
11 ms |
31764 KB |
Output is correct |
10 |
Correct |
13 ms |
31760 KB |
Output is correct |
11 |
Correct |
12 ms |
31700 KB |
Output is correct |
12 |
Correct |
12 ms |
31752 KB |
Output is correct |
13 |
Correct |
12 ms |
31764 KB |
Output is correct |
14 |
Correct |
12 ms |
31696 KB |
Output is correct |
15 |
Correct |
12 ms |
31788 KB |
Output is correct |
16 |
Correct |
13 ms |
31700 KB |
Output is correct |
17 |
Correct |
15 ms |
31740 KB |
Output is correct |
18 |
Correct |
13 ms |
31784 KB |
Output is correct |
19 |
Correct |
13 ms |
31828 KB |
Output is correct |
20 |
Correct |
15 ms |
31828 KB |
Output is correct |
21 |
Correct |
14 ms |
31828 KB |
Output is correct |
22 |
Correct |
14 ms |
31916 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
11 ms |
31700 KB |
Output is correct |
2 |
Correct |
13 ms |
31664 KB |
Output is correct |
3 |
Correct |
11 ms |
31760 KB |
Output is correct |
4 |
Correct |
13 ms |
31648 KB |
Output is correct |
5 |
Correct |
11 ms |
31700 KB |
Output is correct |
6 |
Correct |
12 ms |
31700 KB |
Output is correct |
7 |
Correct |
12 ms |
31756 KB |
Output is correct |
8 |
Correct |
12 ms |
31700 KB |
Output is correct |
9 |
Correct |
11 ms |
31764 KB |
Output is correct |
10 |
Correct |
13 ms |
31760 KB |
Output is correct |
11 |
Correct |
12 ms |
31700 KB |
Output is correct |
12 |
Correct |
12 ms |
31752 KB |
Output is correct |
13 |
Correct |
12 ms |
31764 KB |
Output is correct |
14 |
Correct |
12 ms |
31696 KB |
Output is correct |
15 |
Correct |
12 ms |
31788 KB |
Output is correct |
16 |
Correct |
13 ms |
31700 KB |
Output is correct |
17 |
Correct |
15 ms |
31740 KB |
Output is correct |
18 |
Correct |
13 ms |
31784 KB |
Output is correct |
19 |
Correct |
13 ms |
31828 KB |
Output is correct |
20 |
Correct |
15 ms |
31828 KB |
Output is correct |
21 |
Correct |
14 ms |
31828 KB |
Output is correct |
22 |
Correct |
14 ms |
31916 KB |
Output is correct |
23 |
Runtime error |
38 ms |
64256 KB |
Execution killed with signal 11 |
24 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
12 ms |
31712 KB |
Output is correct |
2 |
Correct |
12 ms |
31700 KB |
Output is correct |
3 |
Correct |
14 ms |
31816 KB |
Output is correct |
4 |
Correct |
14 ms |
31724 KB |
Output is correct |
5 |
Correct |
15 ms |
31760 KB |
Output is correct |
6 |
Correct |
15 ms |
31820 KB |
Output is correct |
7 |
Correct |
15 ms |
31828 KB |
Output is correct |
8 |
Correct |
18 ms |
31768 KB |
Output is correct |
9 |
Correct |
15 ms |
31828 KB |
Output is correct |
10 |
Correct |
16 ms |
31784 KB |
Output is correct |
11 |
Correct |
15 ms |
31780 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
11 ms |
31700 KB |
Output is correct |
2 |
Correct |
13 ms |
31664 KB |
Output is correct |
3 |
Correct |
11 ms |
31760 KB |
Output is correct |
4 |
Correct |
13 ms |
31648 KB |
Output is correct |
5 |
Correct |
11 ms |
31700 KB |
Output is correct |
6 |
Correct |
12 ms |
31700 KB |
Output is correct |
7 |
Correct |
12 ms |
31756 KB |
Output is correct |
8 |
Correct |
12 ms |
31700 KB |
Output is correct |
9 |
Correct |
11 ms |
31764 KB |
Output is correct |
10 |
Correct |
13 ms |
31760 KB |
Output is correct |
11 |
Correct |
12 ms |
31700 KB |
Output is correct |
12 |
Correct |
12 ms |
31752 KB |
Output is correct |
13 |
Correct |
12 ms |
31764 KB |
Output is correct |
14 |
Correct |
12 ms |
31696 KB |
Output is correct |
15 |
Correct |
12 ms |
31788 KB |
Output is correct |
16 |
Correct |
13 ms |
31700 KB |
Output is correct |
17 |
Correct |
15 ms |
31740 KB |
Output is correct |
18 |
Correct |
13 ms |
31784 KB |
Output is correct |
19 |
Correct |
13 ms |
31828 KB |
Output is correct |
20 |
Correct |
15 ms |
31828 KB |
Output is correct |
21 |
Correct |
14 ms |
31828 KB |
Output is correct |
22 |
Correct |
14 ms |
31916 KB |
Output is correct |
23 |
Runtime error |
38 ms |
64256 KB |
Execution killed with signal 11 |
24 |
Halted |
0 ms |
0 KB |
- |