제출 #202302

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
202302		amoo_safar	Collecting Stamps 3 (JOI20_ho_t3)	C++14	100 / 100	145 ms	145528 KiB

ho_t3

#include <bits/stdc++.h>

#define pb push_back
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define debug(x) cerr << #x << " : " << x << '\n'

using namespace std;

typedef long long ll;
typedef long double ld;
typedef string str;
typedef pair<ll, ll> pll;

const int N = 2e2 + 10;
const ll Inf = 1e15;
const int Mx = 1e9 + 1;

ll n, L;
ll x[N], t[N], dp[N][N][N][2];

ll Dis(ll i, ll j){
	return min(abs(i - j), L - abs(i - j));
}

int main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> L;
	for(int i = 0; i < n; i++)
		cin >> x[i];
	for(int i = 0; i < n; i++)
		cin >> t[i];
	ll ans = 0;
	memset(dp, 31, sizeof dp);
	dp[0][0][0][0] = 0;
	dp[0][0][0][1] = 0;
	ll T, I, J;
	for(int i = 0; i < n; i++){
		I = (i ? x[i - 1] : 0);
		for(int j = 0; i + j < n; j++){
			J = (j ? x[n - j] : 0);
			for(int k = 0; k <= i + j; k++){
				T = dp[i][j][k][0] + Dis(I, x[i]);
				dp[i + 1][j][k + (T <= t[i])][0] = min(dp[i + 1][j][k + (T <= t[i])][0], T);

				T = dp[i][j][k][0] + Dis(I, x[n - j - 1]);
				dp[i][j + 1][k + (T <= t[n - j - 1])][1] = min(dp[i][j + 1][k + (T <= t[n - j - 1])][1], T);
				
				T = dp[i][j][k][1] + Dis(J, x[i]);
				dp[i + 1][j][k + (T <= t[i])][0] = min(dp[i + 1][j][k + (T <= t[i])][0], T);
				
				T = dp[i][j][k][1] + Dis(J, x[n - j - 1]);
				dp[i][j + 1][k + (T <= t[n - j - 1])][1] = min(dp[i][j + 1][k + (T <= t[n - j - 1])][1], T);
			}
		}
	}
	for(int i = 0; i <= n; i++)
		for(int k = 0; k <= n; k++)
			if(min(dp[i][n - i][k][0], dp[i][n - i][k][1]) < Inf) ans = max(ans, (ll) k);
	cout << ans << '\n';
	return 0;
}
/*
10 87
9 23 33 38 42 44 45 62 67 78
15 91 7 27 31 53 12 91 89 4
*/

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