Submission #1368361

#TimeUsernameProblemLanguageResultExecution timeMemory
1368361edoCollecting Stamps 3 (JOI20_ho_t3)C++20
100 / 100
96 ms132336 KiB
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int n;
  ll L;
  cin >> n >> L;
  vector<ll> x(n), t(n);
  for(ll &i : x) 
    cin >> i;
  for(ll &i : t)
    cin >> i;

  const ll inf = (1ll << 60);
  vector dp(n + 1, vector(n + 1, vector(2, vector(n + 1, inf))));
  dp[0][0][0][0] = dp[0][0][1][0] = 0;

  auto left = [&](int a) -> ll {
    return x[n - a] - L;
  };
  auto right = [&](int b) -> ll {
    return x[b - 1];
  };

  auto cur_pos = [&](int a, int b, int side) -> ll {
    if(!side) {
      if(!a) return 0;
      return left(a);
    } else {
      if(!b) return 0;
      return right(b);
    }
  };

  auto umin = [](ll& a, ll b) {
    if(a > b) a = b;
  };

  for(int a = 0; a <= n; ++a) {
    for(int b = 0; b <= n; ++b) {
      for(int side = 0; side < 2; ++side) {
        for(int got = 0; got <= n; ++got) {
          ll cur = dp[a][b][side][got];
          if(cur == inf) continue;
          ll from = cur_pos(a, b, side);
          //left
          if(a < n && a + b < n) {
            int na = a + 1;
            int id = n - na;
            ll to = left(na);
            ll nt = cur + abs(from - to);
            umin(dp[na][b][0][got + (nt <= t[id])], nt);
          }
          //right
          if(b < n && b + a < n) {
            int nb = b + 1;
            int id = nb - 1;
            ll to = right(nb);
            ll nt = cur + abs(from - to);
            umin(dp[a][nb][1][got + (nt <= t[id])], nt);
          }
        }
      }
    }
  }

  int ans = 0;
  for(int a = 0; a <= n; ++a) {
    for(int b = 0; b <= n; ++b) {
      for(int side = 0; side < 2; ++side) {
        for(int got = 0; got <= n; ++got) {
          if(dp[a][b][side][got] != inf) {
            ans = max(ans, got);
          }
        }
      }
    }
  }
  cout << ans;

  return 0;
}

#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...