Submission #363875

#	Time	Username	Problem	Language	Result	Execution time	Memory
363875		wind_reaper	Collecting Stamps 3 (JOI20_ho_t3)	C++17	0 / 100	1 ms	364 KiB

ho_t3

#include <bits/stdc++.h>

using namespace std;

const int INF = 2e9;
int32_t main(){
	ios_base::sync_with_stdio(false); 
	cin.tie(NULL); 
	
	int n, l;
	cin >> n >> l; 

	vector<int> pos(n+2), t(n+2);

	for(int i = 1; i <= n; i++)
		cin >> pos[i];

	for(int i = 1; i <= n; i++)
		cin >> t[i];

	t[0] = 0;
	pos[0] = 0;
	pos[n+1] = l; 
	t[n+1] = 0; 
	int64_t dp[n+2][n+2][2][n+2];
	for(int i = 0; i < n + 2; i++)
		for(int j = 0; j < n + 2; j++)
			for(int k = 0; k < n + 2; k++)
				dp[i][j][0][k] = dp[i][j][1][k] = INF; 

	dp[0][n+1][0][0] = dp[0][n+1][1][0] = 0;
	for(int i = 0; i <= n; i++){
		for(int j = n+1; j > i; --j){
			for(int k = 0; k <= n; k++){
				int64_t min_time = min(dp[i][j][0][k] + pos[i+1] - pos[i], dp[i][j][1][k] + l - pos[j] + pos[i+1]);
				dp[i+1][j][0][k + (min_time <= t[i+1])] = min(dp[i+1][j][0][k + (min_time <= t[i+1])], min_time);
				min_time = min(dp[i][j][0][k] + l - pos[j-1] + pos[i], dp[i][j][1][k] + pos[j] - pos[j-1]);
				dp[i][j-1][1][k + (min_time <= t[j-1])] = min(dp[i][j-1][0][k + (min_time <= t[j-1])] , min_time);
			}
		}
	}

	int ans = 0; 
	for(int i = 0; i <= n+1; i++)
		for(int j = 0; j <= n+1; j++)
			for(int k = 0; k <= n+1; k++)
				for(int z = 0; z < 2; z++)
					if(dp[i][j][z][k] < INF){
						ans = max(ans, k);
					}

	cout << ans << '\n';
	return 0; 
}

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