pb_jiang

ABC404E

May 3rd, 2025
529
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.75 KB | None | 0 0
  1. #include <assert.h>
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4. #ifndef __DEBUG__
  5. #define dbg(...) 42
  6. #endif
  7. template <class T>
  8. using mpq = priority_queue<T, vector<T>, greater<T>>;
  9.  
  10. namespace rngs = std::ranges;
  11. using ll = long long;
  12. using a2l = array<ll, 2>;
  13. using pll = pair<ll, ll>;
  14. using vl = vector<ll>;
  15.  
  16. void solve() {
  17.     ll n;
  18.     cin >> n;
  19.     vl cs(n), as(n);
  20.     for (ll i = 1; i < n; ++i)
  21.         cin >> cs[i];
  22.     for (ll i = 1; i < n; ++i)
  23.         cin >> as[i];
  24.  
  25.     vl dp_move(n, LLONG_MAX / 2);
  26.     dp_move[0] = 0;
  27.     for (ll i = 1; i < n; ++i)
  28.         // for (ll j = max(0ll, i - cs[i]); j < i; ++j) {
  29.         for (ll j = i - 1; j >= max(0ll, i - cs[i]); --j) {
  30.             dp_move[i] = min(dp_move[i], dp_move[j] + 1);
  31.             if (as[j])
  32.                 break;
  33.         }
  34.  
  35.     for (ll i = n - 1; i >= 0; --i) {
  36.         if (as[i]) {
  37.             cout << dp_move[i] << '\n';
  38.             return;
  39.         }
  40.     }
  41.  
  42.     /*
  43.     vector<vl> dp_to(n, vl(n, LLONG_MAX / 2));
  44.     for (ll i = 0; i < n; ++i)
  45.         for (ll j = max(0ll, i - cs[i]); j <= i; ++j)
  46.             dp_to[j][i] = 1;
  47.  
  48.     for (ll i = 0; i < n; ++i)
  49.         for (ll j = 0; j < n; ++j) {
  50.         }
  51.     for (ll i = 0; i < n; ++i) {
  52.         dp_to[i][i] = 0;
  53.         for (ll j = i + 1; j < n; ++j) {
  54.  
  55.             dp[i][j] = min(dp[i][j], );
  56.         }
  57.     }
  58.     */
  59. }
  60.  
  61. void solve_wa() {
  62.     ll n;
  63.     cin >> n;
  64.     /*
  65.     vl cs(n), as(n);
  66.     for (auto &x : cs)
  67.         cin >> x;
  68.     for (auto &x : as)
  69.         cin >> x;
  70.     */
  71.     vl cs(n), as(n);
  72.     for (ll i = 1; i < n; ++i)
  73.         cin >> cs[i];
  74.     for (ll i = 1; i < n; ++i)
  75.         cin >> as[i];
  76.  
  77.     vector<vl> g(n + 1);
  78.     for (ll i = 0; i < n; ++i)
  79.         for (ll j = max(0ll, i - cs[i]); j < i; ++j)
  80.             g[i].push_back(j);
  81.  
  82.     vl dist(n, LLONG_MAX / 2);
  83.     dist[0] = 0;
  84.     ll cost = 0;
  85.  
  86.     auto search = [&](auto &&self, ll u, ll fa) -> ll {
  87.         if (dist[u] != LLONG_MAX / 2)
  88.             return as[u] ? 0 : dist[u];
  89.         ll opt = LLONG_MAX / 2;
  90.         for (auto v : g[u])
  91.             opt = min(opt, self(self, v, u) + 1);
  92.  
  93.         return dist[u] = opt;
  94.     };
  95.  
  96.     /*
  97.     for (ll i = n - 1; i > 0; --i) {
  98.         if (as[i] && dist[i] == LLONG_MAX / 2)
  99.             cost += search(search, i, -1);
  100.     }
  101.     */
  102.     for (ll i = 1; i < n; ++i)
  103.         if (as[i] && dist[i] == LLONG_MAX / 2)
  104.             cost += search(search, i, -1);
  105.     dbg(cs);
  106.     dbg(as);
  107.     dbg(dist);
  108.     /*
  109.     for (ll i = 1; i < n; ++i) {
  110.         if (cs[i])
  111.             dfs(dfs, i, -1);
  112.     }
  113.     */
  114.  
  115.     cout << cost << '\n';
  116. }
  117.  
  118. int main(int argc, char **argv) {
  119.     std::ios::sync_with_stdio(false);
  120.     std::cin.tie(nullptr);
  121.  
  122.     solve_wa();
  123.  
  124.     return 0;
  125. };
Advertisement
Add Comment
Please, Sign In to add comment