Submission #827454

#	Time	Username	Problem	Language	Result	Execution time	Memory
827454		MohamedAhmed04	Abduction 2 (JOI17_abduction2)	C++14	23 / 100	39 ms	64308 KiB

abduction2

#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] <= 5) ;
		for(int k = 1 ; k <= m ; ++k)
			assert(cntc[k] <= 5) ;
	}
	return 0 ;
}		

• Subtask 1: 13 / 13
• Subtask 2: 10 / 10
• Subtask 3: 0 / 17
• Subtask 4: 0 / 4
• Subtask 5: 0 / 56