Submission #1308237

#	Time	Username	Problem	Language	Result	Execution time	Memory
1308237		lyra_g13	Journey (NOI18_journey)	C++20	43 / 100	10 ms	572 KiB

journey

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

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

  ll n, maxnights, h;
  cin >> n >> maxnights >> h;

  vector<vector<ll>> dp(n, vector<ll>(maxnights));
  vector<vector<pair<ll, ll>>> adj(n);
  for (int i = 0; i < n - 1; i++) {
    for (int j = 0; j < h; j++) {
      ll a, b;
      cin >> a >> b;
      if (a > i)
        adj[i].push_back({a, b});
    }
  }

  dp[0][0] = 1;

  for (int i = 0; i < n; i++) {
    for (auto [x, y] : adj[i]) {
      for (int p = 0; p < maxnights; p++) {
        for (int j = y; p + j < maxnights; j++) {
          dp[x][p + j] = min(dp[x][p + j] + dp[i][p], 500000000LL);
        }
      }
    }
  }

  for (int i = 0; i < maxnights; i++) {
    cout << dp[n - 1][i] << "\n";
  }
}

• Subtask 1: 20 / 20
• Subtask 2: 23 / 23
• Subtask 3: 0 / 26
• Subtask 4: 0 / 31