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;
#define fi first
#define se second
#define owo ios_base::sync_with_stdio(0);cin.tie(0);
typedef pair<int,int> pii;
const int MAXN = 55555;
int a[MAXN],b[MAXN];
int hmx[2][MAXN],wmx[2][MAXN];
int h,w,q;
typedef long long int ll;
map<int,ll>dp[2][MAXN];
ll solve(ll i,ll j,ll k){
if(dp[k][i].find(j) != dp[k][i].end())return dp[k][i][j];
if(!k){
dp[0][i][j] = -1e9;
for(ll jj=j+1;jj<w;jj++){
if(b[jj] > a[i]){
dp[0][i][j] = max(dp[0][i][j],solve(i,jj,1)+jj-j);
break;
}
}
for(ll jj=j-1;jj>=0;jj--){
if(b[jj] > a[i]){
dp[0][i][j] = max(dp[0][i][j],solve(i,jj,1)+j-jj);
break;
}
}
if(dp[0][i][j] == -1e9)dp[0][i][j] = max(w-1-j,j);
}else{
dp[1][i][j] = -1e9;
for(ll ii=i+1;ii<h;ii++){
if(a[ii] > b[j]){
dp[1][i][j] = max(dp[1][i][j],solve(ii,j,0) + ii-i);
break;
}
}
for(ll ii=i-1;ii>=0;ii--){
if(a[ii] > b[j]){
dp[1][i][j] = max(dp[1][i][j],solve(ii,j,0) + i-ii);
break;
}
}
if(dp[1][i][j] == -1e9)dp[1][i][j] = max(h-1-i,i);
}
return dp[k][i][j];
}
int main()
{
owo
cin>>h>>w>>q;
for(int i=0;i<h;i++)cin>>a[i];
for(int i=0;i<w;i++)cin>>b[i];
for(int i=0;i<h;i++){
hmx[0][i] = a[i];
if(i)hmx[0][i] = max(hmx[0][i],hmx[0][i-1]);
}
for(int i=h-1;i>=0;i--){
hmx[1][i] = a[i];
if(i!=h-1)hmx[1][i] = max(hmx[1][i],hmx[1][i+1]);
}
for(int i=0;i<w;i++){
wmx[0][i] = b[i];
if(i)wmx[0][i] = max(wmx[0][i],wmx[0][i-1]);
}
for(int i=w-1;i>=0;i--){
wmx[1][i] = b[i];
if(i!=w-1)wmx[1][i] = max(wmx[1][i],wmx[1][i+1]);
}
while(q--){
int i,j;
cin>>i>>j;
i--;
j--;
ll ans = max(solve(i,j,0),solve(i,j,1));
cout<<ans<<'\n';
}
}
# | 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... |