Submission #628537

#	Time	Username	Problem	Language	Result	Execution time	Memory
628537		Abrar_Al_Samit	Collecting Stamps 3 (JOI20_ho_t3)	C++17	100 / 100	269 ms	33188 KiB

ho_t3

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

const int MX = 203;
const int INF = 1e9+10;

int n, L;
int pos[MX], T[MX];
int dp[MX][MX][MX];

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 k) {
  if(k==0) return dist(0, i);
  if(n-(abs(j-i)-1)<k) return INF;
  int &ret = dp[i][j][k];
  if(ret!=-1) return ret;

  ret = INF;
  if(i<=j) {
    if(i>1) {
      if(solve(i-1, j, k-1)+dist(i, i-1)<=T[i]) {
        ret = min(ret, solve(i-1, j, k-1)+dist(i, i-1));
      }
      if(solve(i-1, j, k)!=INF) {
        ret = min(ret, solve(i-1, j, k)+dist(i, i-1));
      }
    } else {
      if(j==n && dist(0, i)<=T[i] && k==1) {
        ret = min(ret, dist(0, i));
      } 
    }
    if(j+1<=n) {
      if(solve(j+1, i, k-1)+dist(j+1, i)<=T[i]) {
        ret = min(ret, solve(j+1, i, k-1)+dist(j+1, i));
      }
      if(solve(j+1, i, k)!=INF) {
        ret = min(ret, solve(j+1, i, k)+dist(j+1, i));
      }
    }
  } else {
    if(i+1<=n) {
      if(solve(i+1, j, k-1)+dist(i, i+1)<=T[i]) {
        ret = min(ret, solve(i+1, j, k-1)+dist(i, i+1));
      }
      if(solve(i+1, j, k)!=INF) {
        ret = min(ret, solve(i+1, j, k)+dist(i, i+1));
      }
    }
    if(j>1) {
      if(solve(j-1, i, k-1)+dist(i, j-1)<=T[i]) {
        ret = min(ret, solve(j-1, i, k-1)+dist(i, j-1));
      }
      if(solve(j-1, i, k)!=INF) {
        ret = min(ret, solve(j-1, i, k)+dist(i, j-1));
      }
    } else {
      if(i==n && dist(0, i)<=T[i] && k==1) {
        ret = min(ret, dist(0, i));
      }
    }
  }
  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];
  }

  memset(dp, -1, sizeof dp);
  int ans = 0;
  for(int i=1; i<=n; ++i) {
    for(int j=1; j<=n; ++j) {
      for(int k=1; k<=n; ++k) {
        if(solve(i, j, k)<INF) {
          ans = max(ans, k);
        }
      }
    }
  }
  cout<<ans<<'\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: 10 / 10
• Subtask 4: 75 / 75