제출 #510043

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
510043		CSQ31	Collecting Stamps 3 (JOI20_ho_t3)	C++17	100 / 100	173 ms	130804 KiB

ho_t3

#include <bits/stdc++.h>
using namespace std;
long long int dp[205][205][205][2];
int n,L,x[400],t[400];
const long long int INF = 1e18;
int dist(int l,int r){
	if(r >= l)return x[r] - x[l];
	return L-x[l] + x[r];
}
int main()
{
	cin>>n>>L;
	for(int i=1;i<=n;i++)cin>>x[i];
	for(int i=1;i<=n;i++)cin>>t[i];
	for(int i=0;i<=n;i++){
		for(int j=0;j<=n;j++)
			for(int k=0;k<=n+1;k++)dp[i][j][k][0] = dp[i][j][k][1] = INF;
	}
	t[0] = -1;
	dp[0][0][0][0] = 0;
	n++;
	int ans = 0;
	for(int i=0;i<n;i++){
		for(int l=0;l<n;l++){
			for(int k=0;k<=n;k++){
				int r = (l+i)%n;
				for(int c=0;c<2;c++){
					if(dp[l][r][k][c] == INF)continue;
					//cout<<l<<" "<<r<<" "<<k<<" "<<c<<" "<<dp[l][r][k][c]<<'\n';
					ans = max(ans,k);
					int s = c?r:l;
					int ln = (l-1+n)%n;
					int d = dist(ln,s);
					long long int v = dp[l][r][k][c] + d;
					dp[ln][r][k][0] = min(dp[ln][r][k][0],v);
					if(t[ln] >= v)dp[ln][r][k+1][0] = min(dp[ln][r][k+1][0],v);
					
					int rn = (r+1)%n;
					d = dist(s,rn);
					v = dp[l][r][k][c] + d;
					dp[l][rn][k][1] = min(dp[l][rn][k][1],v);
					if(t[rn] >= v)dp[l][rn][k+1][1] = min(dp[l][rn][k+1][1],v);
				}
			}
			
		}
	}
	
	cout<<ans<<'\n';
	
}

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