Submission #290860

#	Time	Username	Problem	Language	Result	Execution time	Memory
290860		cheissmart	Collecting Stamps 3 (JOI20_ho_t3)	C++14	100 / 100	74 ms	65024 KiB

ho_t3

#include <bits/stdc++.h>
#define F first
#define S second
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define ALL(v) (v).begin(), (v).end()
#define debug(x) cerr << #x << " " << (x) << endl;
#define V vector

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef V<int> vi;

const int N = 202, INF = 0x3f3f3f3f;

int x[N], dp[N][N][N][2], t[N];

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	int n, l;
	cin >> n >> l;
	for(int i = 0; i < n; i++) cin >> x[i];
	for(int i = 0; i < n; i++) cin >> t[i];
	memset(dp, 0x3f, sizeof dp);
	if(x[0] <= t[0]) dp[1][0][1][0] = x[0];
	else dp[1][0][0][0] = x[0];
	if(l-x[n-1] <= t[n-1]) dp[0][1][1][1] = l-x[n-1];
	else dp[0][1][0][1] = l-x[n-1];
	for(int i = 0; i <= n; i++) {
		for(int j = 0; j + i <= n - 1; j++) {
			for(int k = 0; k <= i + j; k++) {
				if(dp[i][j][k][0] != INF) {
					//cerr << "dp[" << i << "][" << j << "][" << k << "][0] = " << dp[i][j][k][0] << endl;
					// 0
					if(dp[i][j][k][0] + x[i]-x[i-1] <= t[i])
						dp[i + 1][j][k+1][0] = min(dp[i + 1][j][k+1][0], dp[i][j][k][0] + x[i]-x[i-1]);
					else
						dp[i + 1][j][k][0] = min(dp[i + 1][j][k][0], dp[i][j][k][0] + x[i]-x[i-1]);
					// 1
					if(dp[i][j][k][0] + x[i - 1] + l - x[n-j-1] <= t[n-j-1])
						dp[i][j + 1][k+1][1] = min(dp[i][j + 1][k+1][1], dp[i][j][k][0] + x[i - 1] + l - x[n-j-1]);
					else
						dp[i][j + 1][k][1] = min(dp[i][j + 1][k][1], dp[i][j][k][0] + x[i - 1] + l - x[n-j-1]);
				}
				if(dp[i][j][k][1] != INF) {
					//cerr << "dp[" << i << "][" << j << "][" << k << "][1] = " << dp[i][j][k][1] << endl;
					// 0
					if(dp[i][j][k][1] + l-x[n-j]+x[i] <= t[i])
						dp[i + 1][j][k+1][0] = min(dp[i + 1][j][k+1][0], dp[i][j][k][1] + l-x[n-j]+x[i]);
					else
						dp[i + 1][j][k][0] = min(dp[i + 1][j][k][0], dp[i][j][k][1] + l-x[n-j]+x[i]);
					// 1
					if(dp[i][j][k][1] + x[n-j] - x[n-j-1] <= t[n-j-1])
						dp[i][j + 1][k+1][1] = min(dp[i][j + 1][k+1][1], dp[i][j][k][1] + x[n-j] - x[n-j-1]);
					else
						dp[i][j + 1][k][1] = min(dp[i][j + 1][k][1], dp[i][j][k][1] + x[n-j] - x[n-j-1]);
				}
			}
		}
	}
	int mx = 0;
	for(int i = 0; i <= n; i++)
		for(int j = 0; j <= n; j++)
			for(int k = 0; k <= i + j; k++) {
				if(dp[i][j][k][0] != INF) mx = max(mx, k);
				if(dp[i][j][k][1] != INF) mx = max(mx, k);
			}
	cout << mx << endl;
	
}

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