Submission #389622

#	Time	Username	Problem	Language	Result	Execution time	Memory
389622		mariowong	Collecting Stamps 3 (JOI20_ho_t3)	C++14	0 / 100	1 ms	716 KiB

ho_t3

#include <bits/stdc++.h>

using namespace std;

struct stamps{
	long long d,t;
}a[205];

long long dp[205][205][205][5],n,l,ans;
int main(){
	ios::sync_with_stdio(false);
	cin >> n >> l;
	for (int i=1;i<=n;i++){
		cin >> a[i].d;
	}
	for (int i=1;i<=n;i++){
		cin >> a[i].t;
	}
	for (int i=0;i<=n+1;i++){
		for (int j=0;j<=n+1;j++){
			for (int k=0;k<=n;k++){
				dp[i][j][k][0]=dp[i][j][k][1]=1e18;
			}
		}
	}
	a[n+1].d=l; 
	dp[0][n+1][0][0]=dp[0][n+1][0][1]=0;
	for (int i=0;i<=n;i++){
		for (int j=n+1;j>i;j--){
			for (int k=0;k<=max(0LL,n-j+1)+i;k++){
				if (i != 0){
					if (k > 0 && dp[i-1][j][k-1][0]+a[i].d-a[i-1].d <= a[i].t)
					dp[i][j][k][0]=min(dp[i][j][k][0],dp[i-1][j][k-1][0]+a[i].d-a[i-1].d);
					dp[i][j][k][0]=min(dp[i][j][k][0],dp[i-1][j][k][0]+a[i].d-a[i-1].d);
					
					if (k > 0 && j != n+1 && dp[i-1][j][k-1][1]+l-a[j].d+a[i].d <= a[i].t)
					dp[i][j][k][0]=min(dp[i][j][k][0],dp[i-1][j][k-1][1]+l-a[j].d+a[i].d);
					if (j != n+1)
					dp[i][j][k][0]=min(dp[i][j][k][0],dp[i-1][j][k][1]+l-a[j].d+a[i].d);
				}
				if (j != n+1){
					if (k > 0 && dp[i][j+1][k-1][1]+a[j+1].d-a[j].d <= a[j].t)
					dp[i][j][k][1]=min(dp[i][j][k][1],dp[i][j+1][k-1][1]+a[j+1].d-a[j].d);
					dp[i][j][k][1]=min(dp[i][j][k][1],dp[i][j+1][k][1]+a[j+1].d-a[j].d);
				//	cout << i << " " << j << " " << k << " " << dp[i][j+1][k-1][1] << " " << a[j+1].d<< " " << a[j].d << " " << l-a[j+1].d+a[j].d << "\n";
					if (k > 0 && i != 0 && dp[i][j-1][k][0]+l-a[j].d+a[i].d <= a[j].t)
					dp[i][j][k][1]=min(dp[i][j][k][1],dp[i][j+1][k-1][0]+l-a[j].d+a[i].d);
					if (i != 0)
					dp[i][j][k][1]=min(dp[i][j][k][1],dp[i][j+1][k][0]+l-a[j].d+a[i].d);
				}
			}
		}
	}
	for (int i=0;i<=n;i++){
		for (int j=n+1;j>i;j--){
			if (i+1 == j){
				for (long long k=1;k<=n;k++){
					if (dp[i][j][k][0] != 1e18 || dp[i][j][k][1] != 1e18)
					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