Submission #207746

#	Time	Username	Problem	Language	Result	Execution time	Memory
207746		MohamedAhmed04	Collecting Stamps 3 (JOI20_ho_t3)	C++14	0 / 100	5 ms	504 KiB

ho_t3

#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][a] + dist(i , j , a , 0) ;
					y = dp[i][j+1][taken][a] + dist(i , j , a , 1) ;
					dp[i][j][taken][a] = min(x , y) ;
					if(taken)
					{
						x = dp[i-1][j][taken-1][a] + dist(i , j , a , 0) ;
						y = dp[i][j+1][taken-1][a] + 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 ;
}		

• Subtask 1: 0 / 5
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 75