Submission #207932

#	Time	Username	Problem	Language	Result	Execution time	Memory
207932		YJU	Collecting Stamps 3 (JOI20_ho_t3)	C++14	0 / 100	85 ms	131324 KiB

ho_t3

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef long double ld;
const ll MOD=1e9+7;
const ll N=2e2+3;
const ll INF=(1LL<<62);
const ld pi=3.14159265359;
#define REP(i,n) for(ll i=0;i<n;i++)
#define REP1(i,n) for(ll i=1;i<=n;i++)
#define pb push_back
#define mp make_pair
#define X first
#define Y second
#define setp setprecision
#define lwb lower_bound
#define SZ(a) (ll)a.size()

ll n,L,x[N],t[N],dp[N][N][N],dq[N][N][N],ans; 

ll dis(ll a,ll b){
	if(a>b)swap(a,b);
	return min(x[b]-x[a],L-x[b]+x[a]);
}
 
int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	cin>>n>>L;
	REP(i,n)cin>>x[i];
	REP(i,n)cin>>t[i];
	REP(i,N)REP(j,N)REP(k,N)dp[i][j][k]=dq[i][j][k]=INF;
	dp[0][0][0]=x[0];dp[n-1][n-1][0]=L-x[n-1];
	if(x[0]<=t[0])dp[0][0][1]=x[0];
	if((L-x[n-1])<=t[n-1])dp[n-1][n-1][1]=L-x[n-1];
	dq[0][0][0]=x[0];dq[n-1][n-1][0]=L-x[n-1];
	if(x[0]<=t[0])dq[0][0][1]=x[0];
	if((L-x[n-1])<=t[n-1])dq[n-1][n-1][1]=L-x[n-1];
	for(ll l=0;l<=n;l++){
		for(ll i=(n-1-l%n+n)%n;i%n!=0;i++){
			for(ll j=0;j<=l+1;j++){
				dp[i][(i+l)%n][j]=min(dp[i][(i+l)%n][j],dq[i][(i+l)%n][j]+dis((i+l)%n,i));
				dq[i][(i+l)%n][j]=min(dq[i][(i+l)%n][j],dp[i][(i+l)%n][j]+dis((i+l)%n,i));
				if(l==n)continue;
				dp[(i+n-1)%n][(i+l)%n][j]=min(dp[(i+n-1)%n][(i+l)%n][j],min(dp[i][(i+l)%n][j]+dis((i+n-1)%n,i),dq[i][(i+l)%n][j]+dis((i+l)%n,(i+n-1)%n)));
				if(min(dp[i][(i+l)%n][j]+dis((i+n-1)%n,i),dq[i][(i+l)%n][j]+dis((i+l)%n,(i+n-1)%n))<=t[(i+n-1)%n])dp[(i+n-1)%n][(i+l)%n][j+1]=min(dp[(i+n-1)%n][(i+l)%n][j+1],dp[(i+n-1)%n][(i+l)%n][j]);
				dq[i][(i+l+1)%n][j]=min(dq[i][(i+l+1)%n][j],min(dq[i][(i+l)%n][j]+dis((i+l)%n,(i+l+1)%n),dp[i][(i+l)%n][j]+dis(i,(i+l+1)%n)));
				if(min(dq[i][(i+l)%n][j]+dis((i+l)%n,(i+l+1)%n),dp[i][(i+l)%n][j]+dis(i,(i+l+1)%n))<=t[(i+l+1)%n])dq[i][(i+l+1)%n][j+1]=min(dq[i][(i+l+1)%n][j+1],dq[i][(i+l+1)%n][j]);
			}
		}
	}
	REP(i,N)REP(j,N)REP(k,N){
		if(dp[i][j][k]<INF||dq[i][j][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