Submission #580260

#	Time	Username	Problem	Language	Result	Execution time	Memory
580260		HeyYouNotYouYou	Collecting Stamps 3 (JOI20_ho_t3)	C++14	15 / 100	2101 ms	132416 KiB

ho_t3

#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N = 250,INF=1e12;
int n , L;
int x[N] , t[N];
map<pair<pair<int,int>,pair<int,int>>,int>dp;
int solve(int l ,int r , int time , int pos){
  if(l==r) return 0;
  if(dp.count({{l,r},{time,pos}})) 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: 10 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 75