Submission #624804

#TimeUsernameProblemLanguageResultExecution timeMemory
624804CSQ31Abduction 2 (JOI17_abduction2)C++17
44 / 100
1128 ms14836 KiB
#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; typedef long long int ll; const int MAXN = 55555; int a[MAXN],b[MAXN]; ll h,w,q; 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]; dp[k][i][j] = -1e9; if(!k){ 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{ 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]; 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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...