Submission #580258

#	Time	Username	Problem	Language	Result	Execution time	Memory
580258		HeyYouNotYouYou	Collecting Stamps 3 (JOI20_ho_t3)	C++14	5 / 100	188 ms	273724 KiB

ho_t3

#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N = 205,INF=1e12;
int n , L;
int x[N] , t[N];
int dp[N][N][N][2];
int solve(int l ,int r , int time , int pos){
  if(l==r) return 0;
  if(dp[l][r][time][pos]!=-1) return dp[l][r][time][pos];
  if(pos){
    return dp[l][r][time][pos]=max(
    solve(l,r+1,time+(x[r+1]-x[r]),1)+(time+(x[r+1]-x[r])<=t[r+1]),
    solve(l,r+1,time+(L-x[l])+x[r],0)+(time+(L-x[l])+x[r]<=t[l]));
  }
  else{
    return dp[l][r][time][pos]=max(
    solve(l-1,r,time+(x[l]-x[l-1]),0)+(time+(x[l]-x[l-1])<=t[l-1]),
    solve(l-1,r,time+(L-x[l])+x[r],1)+(time+(L-x[l])+x[r]<=t[r]));
  }
}
int32_t main()
{
  //freopen("abc.in", "r", stdin);
  cin >> n >> L;
  memset(dp,-1,sizeof dp);
  for(int i = 1 ; i <= n ; i ++) cin>>x[i];
  for(int i = 1 ; i <= n ; i ++) cin>>t[i];
  cout<<max(solve(n,1,L-x[n],0)+(L-x[n]<=t[n]),solve(n,1,x[1],1)+(x[1]<=t[1]));
}

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