제출 #1289093

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1289093		tunademayo	Collecting Stamps 3 (JOI20_ho_t3)	C++20	0 / 100	1 ms	580 KiB

ho_t3

#include<bits/stdc++.h>
using namespace std;

#define ll long long 

const bool Multitest = 0;

const int N = 205;

void minimize(ll& a, ll b)
{
	a = min(a, b);
}

int x[N], t[N]; int n, k;

ll dp[N][N][N], dis[N][N];

bool check(int l, int r, bool check, int val)
{
	if(check == 1)
	{
		return t[r] >= val + dis[min(l, r)][max(l, r)];
	}
	
	return t[r] >= val + dis[max(l, r)][min(l, r)];
}

void work()
{
	cin >> n >> k;
	
	for(int i = 1 ; i <= n ; i++) cin >> x[i];
	for(int i = 1 ; i <= n ; i++) cin >> t[i];	
	
	x[n + 1] = k;
	
	for(int i = 0 ; i <= n + 1 ; i++)
	{
		for(int j = 0 ; j <= n + 1 ; j++)
		{
			if(i == j) continue;
			
			if(i < j) dis[i][j] = x[j] - x[i];
			else 
			{
				dis[i][j] = k - (x[i] - x[j]);
			}
		}
	}
	
	for(int i = 0 ; i <= n + 1 ; i++)
	{
		for(int j = 0 ; j <= n + 1 ; j++)
		{
			for(int cnt = 0 ; cnt <= n + 1 ; cnt++)
			{
				dp[i][j][cnt] = 1e9 + 10;
			}
		}
	}
	
	dp[0][n + 1][0] = 0;
	dp[n + 1][0][0] = 0;
	
	int ans = 0;
	
	for(int len = n + 2 ; len >= 1 ; len--)
	{
		for(int l = 0 ; l + len - 1 <= n + 1 ; l++)
		{
			int r = l + len - 1;
			
			for(int cnt = 0 ; cnt <= l + (n + 1) - r ; cnt++)
			{
//				cout << l << ' ' << r << ' ' << cnt << ' ' << dp[l][r][cnt] << ' ' << t[l] << ' ' << ans << '\n';
//				cout << l << ' ' << r << ' ' << cnt << ' ' << dp[r][l][cnt] << ' ' << t[r] << ' ' << ans << '\n';
				
				if(ans < cnt && dp[l][r][cnt] <= t[l]) ans = cnt;
				if(ans < cnt && dp[r][l][cnt] <= t[r]) ans = cnt;
				
				for(int x = l ; x <= r ; x++)
				{
					if(check(r, x, 1, dp[r][l][cnt]) && x != r) minimize(dp[x][l][cnt + 1], dp[r][l][cnt] + dis[x][r]);
					if(check(r, x, 0, dp[r][l][cnt]) && x != r) minimize(dp[x][r][cnt + 1], dp[r][l][cnt] + dis[r][x]);
					
					if(check(l, x, 1, dp[l][r][cnt]) && x != l) minimize(dp[x][r][cnt + 1], dp[l][r][cnt] + dis[l][x]);
					if(check(r, x, 0, dp[l][r][cnt]) && x != l) minimize(dp[x][l][cnt + 1], dp[l][r][cnt] + dis[x][l]);
				}
			}
		}
	}
	
//	cout << dp[n - 4][0][5] << '\n'; 
	
	cout << ans;
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);	cout.tie(0);
	
	int q = 1;
	
	if(Multitest)	cin >> q;
	
	while(q--) work();
}

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