제출 #207748

#제출 시각아이디문제언어결과실행 시간메모리
207748MohamedAhmed04Collecting Stamps 3 (JOI20_ho_t3)C++14
100 / 100
115 ms135288 KiB
#include <bits/stdc++.h>
 
using namespace std ;
 
const int inf = 2e9 ;
const int MAX = 210 ;
 
long long X[MAX] , T[MAX] ;
int n ;
long long L ;
long long dp[MAX][MAX][MAX][2] ;
 
long long dist(int i , int j , int a , int b)
{
	if(b == 0)
	{
		if(a == 0)
			return (X[i] - X[i-1]) ;
		else
			return (L - X[j] + X[i-1]) ;
	}
	else
	{
		if(a == 1)
			return (X[j+1] - X[j]) ;
		else
			return (X[i] + L - X[j+1]) ;
	}
}
 
int main()
{
	ios_base::sync_with_stdio(0) ;
	cin.tie(0) ;
	cin>>n>>L ;
	for(int i = 1 ; i <= n ; ++i)
		cin>>X[i] ;
	for(int i = 1 ; i <= n ; ++i)
		cin>>T[i] ;
	for(int i = 0 ; i <= n+1 ; ++i)
	{
		for(int j = 0 ; j <= n+1 ; ++j)
		{
			for(int taken = 1 ; taken <= n+1 ; ++taken)
			{
				for(int a = 0 ; a <= 1 ; ++a)
					dp[i][j][taken][a] = inf ;
			}
		}
	}
	X[n+1] = L ;
	int ans = 0 ;
	for(int i = 1 ; i <= n ; ++i)
	{
		for(int j = n ; j >= i ; --j)
		{
			for(int taken = 0 ; taken <= n ; ++taken)
			{
				for(int a = 0 ; a <= 1 ; ++a)
				{
					long long x , y ;
					x = dp[i-1][j][taken][0] + dist(i , j , a , 0) ;
					y = dp[i][j+1][taken][1] + dist(i , j , a , 1) ;
					dp[i][j][taken][a] = min(x , y) ;
					if(taken)
					{
						x = dp[i-1][j][taken-1][0] + dist(i , j , a , 0) ;
						y = dp[i][j+1][taken-1][1] + dist(i , j , a , 1) ;
						if((a == 0 && min(x , y) <= T[i]) || (a == 1 && min(x , y) <= T[j]))
						{
							dp[i][j][taken][a] = min(dp[i][j][taken][a] , min(x , y)) ;
							ans = max(ans , taken) ;
						}
					}
				}
			}
		}
	}
	return cout<<ans<<"\n" , 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...