제출 #1285652

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1285652		Jawad_Akbar_JJ	Collecting Stamps 3 (JOI20_ho_t3)	C++20	100 / 100	111 ms	129452 KiB

ho_t3

#include <iostream>
#include <algorithm>

using namespace std;
#define int long long
const int N = 202;
int x[N], t[N], dp[N][N][N][2];

signed main(){
	int n, L;
	cin>>n>>L;

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

	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 l : {0, 1})
					dp[i][j][k][l] = 1e17;
	}

	dp[0][0][n+1][0] = 0;

	for (int i=0;i<=n;i++){
		for (int j=0;j<n;j++){
			for (int k=n+1;k > j + 1;k--){
				// currently at left side
				bool hit = t[j + 1] >= dp[i][j][k][0] + (x[j+1] - x[j]);
				dp[i+hit][j+1][k][0] = min(dp[i+hit][j+1][k][0], dp[i][j][k][0] + (x[j+1] - x[j]));

				hit = t[k - 1] >= dp[i][j][k][0] + x[j] + (L - x[k - 1]);
				dp[i+hit][j][k-1][1] = min(dp[i+hit][j][k-1][1], dp[i][j][k][0] + x[j] + (L - x[k-1]));

				// currently at right side
				hit = t[k - 1] >= dp[i][j][k][1] + x[k] - x[k-1];
				dp[i+hit][j][k-1][1] = min(dp[i+hit][j][k-1][1], dp[i][j][k][1] + x[k] - x[k-1]);

				hit = t[j+1] >= dp[i][j][k][1] + L - x[k] + x[j+1];
				dp[i+hit][j+1][k][0] = min(dp[i+hit][j+1][k][0], dp[i][j][k][1] + L - x[k] + x[j + 1]);
			}
		}
	}

	for (int i=n;i>=0;i--){
		for (int j=0;j<=n;j++)
			for (int k=n+1;k >= j + 1;k--)
				for (int l : {0, 1})
					if (dp[i][j][k][l] != 1e17)
						return cout<<i<<endl, 0;
	}
}

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