Submission #627737

#	Time	Username	Problem	Language	Result	Execution time	Memory
627737		Abrar_Al_Samit	Collecting Stamps 3 (JOI20_ho_t3)	C++17	15 / 100	151 ms	14364 KiB

ho_t3

#include<bits/stdc++.h>
using namespace std;

const int MX = 203;

int n, L;
int pos[MX], T[MX];
map<tuple<int,int,int>, int>dp;
int MAXT;

int dist(int i, int j) {
  int ret = abs(pos[i]-pos[j]);
  return min(ret, L-ret);
}
int solve(int i, int j, int CLOCK) {
  if(CLOCK>MAXT) return 0;
  auto it = dp.lower_bound(make_tuple(i, j, CLOCK));
  if(it!=dp.begin()) {
    it = prev(it);
    if(get<0>(it->first)==i && get<1>(it->first)==j) {
      CLOCK = min(CLOCK, get<2>(it->first));
    }
  }
  if(dp.count({i, j, CLOCK})) return dp[{i, j, CLOCK}];
  int ret = 0;
  if(i<j) {
    if(i<n) ret = max(ret, solve(j, i+1, CLOCK+dist(i, j)));
    else ret = max(ret, solve(j, j, CLOCK+dist(i, j)));

    if(i<n) ret = max(ret, solve(i+1, j, CLOCK+dist(i, i+1)));    
  } else if(i>j) {
    if(i>1) ret = max(ret, solve(i-1, j, CLOCK+dist(i, i-1)));
    if(i>1) ret = max(ret, solve(j, i-1, CLOCK+dist(j, i)));
    else ret = max(ret, solve(j, j, CLOCK+dist(j, i)));
  }
  ret += CLOCK<=T[i];
  dp[{i, j, CLOCK}] = ret;
  assert(dp.size()<=3000000);
  return ret;
}
void PlayGround() {
  cin>>n>>L;
  for(int i=1; i<=n; ++i) {
    cin>>pos[i];
  }
  for(int i=1; i<=n; ++i) {
    cin>>T[i];
    MAXT = max(MAXT, T[i]);
  }
  cout << max(solve(1, n, pos[1]), solve(n, 1, L-pos[n])) << '\n';
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  PlayGround();
  return 0;
}

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