Submission #364275

#	Time	Username	Problem	Language	Result	Execution time	Memory
364275		tushar_2658	Collecting Stamps 3 (JOI20_ho_t3)	C++14	100 / 100	179 ms	132204 KiB

ho_t3

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

const int maxn = 205;
using ll = long long;
ll inf = 1e18;

ll x[maxn], t[maxn];
ll L;
int n;
ll dp[maxn][maxn][maxn][2];

int main(int argc, char const *argv[])
{
  ios::sync_with_stdio(false);
  cin.tie(0);

  cin >> n >> L;
  for(int i = 1; i <= n; ++i){
    cin >> x[i];
  }
  for(int i = 1; i <= n; ++i){
    cin >> t[i];
  }
  x[0] = 0;
  x[n + 1] = L;
  t[n + 1] = -1;
  t[0] = -1;
  for(int i = 0; i <= n + 1; ++i)for(int j = 0; j <= n + 1; ++j)for(int k = 0; k <= n + 1; ++k)for(int l = 0; l < 2; ++l)dp[i][j][k][l] = inf;
  dp[0][n + 1][0][0] = dp[0][n + 1][0][1] = 0;
  for(int l = n + 1; l > 1; --l){
    for(int i = 0, j = i + l; j <= n + 1; ++i, ++j){
      for(int k = 0; k <= n + 1; ++k){
        for(int pos = 0; pos < 2; ++pos){
          if(pos == 0){
            ll mn = dp[i][j][k][pos];
            if(t[i + 1] >= mn + llabs(x[i + 1] - x[i])){
              dp[i + 1][j][k + 1][pos] = min(dp[i + 1][j][k + 1][pos], mn + llabs(x[i + 1] - x[i]));
            }else {
              dp[i + 1][j][k][pos] = min(dp[i + 1][j][k][pos], mn + llabs(x[i + 1] - x[i]));
            }
            if(t[j - 1] >= mn + L - llabs(x[j - 1] - x[i])){
              dp[i][j - 1][k + 1][1] = min(dp[i][j - 1][k + 1][1], mn + L - llabs(x[j - 1] - x[i]));
            }else {
              dp[i][j - 1][k][1] = min(dp[i][j - 1][k][1], mn + L - llabs(x[j - 1] - x[i]));
            }
          }else {
            ll mn = dp[i][j][k][pos];
            ll X = mn + L - llabs(x[j] - x[i + 1]);
            if(t[i + 1] >= X){
              dp[i + 1][j][k + 1][0] = min(dp[i + 1][j][k + 1][0], X);
            }else {
              dp[i + 1][j][k][0] = min(dp[i + 1][j][k][0], X);
            }
            X = mn + x[j] - x[j - 1];
            if(t[j - 1] >= X){
              dp[i][j - 1][k + 1][pos] = min(dp[i][j - 1][k + 1][pos], X);
            }else {
              dp[i][j - 1][k][pos] = min(dp[i][j - 1][k][pos], X);
            }
          }
        }
      }
    }
  }
  int ans = 0;
  for(int k = 0; k <= n; ++k){
    for(int i = 0; i <= n + 1; ++i){
      for(int j = i + 1; j <= n + 1; ++j){
        for(int pos = 0; pos < 2; ++pos){
          if(dp[i][j][k][pos] < inf){
            ans = max(ans, k);
          }
        }
      }
    }
  }
  cout << ans << '\n';

  return 0;
}

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