Submission #827443

#TimeUsernameProblemLanguageResultExecution timeMemory
827443MohamedAhmed04Abduction 2 (JOI17_abduction2)C++14
0 / 100
40 ms64188 KiB
#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]) cntr[i]++ ; else 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 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...