This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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 cntr[MAX] , cntc[MAX] ;
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 ;
if(a[i] > b[j] && !flag)
cntr[i]++ ;
else if(!flag)
cntc[j]++ ;
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--)
{
memset(cntr , 0 , sizeof(cntr)) ;
memset(cntc , 0 , sizeof(cntc)) ;
int i , j ;
cin>>i>>j ;
cout<<solve(i , j , 1)<<"\n" ;
for(int k = 1 ; k <= n ; ++k)
assert(cntr[k] <= 3) ;
for(int k = 1 ; k <= m ; ++k)
assert(cntc[k] <= 3) ;
}
return 0 ;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |