Submission #1308242

#	Time	Username	Problem	Language	Result	Execution time	Memory
1308242		lyra_g13	Journey (NOI18_journey)	C++20	0 / 100	1 ms	568 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++) {
        ll add = min(500000001LL, dp[i][p]);
        dp[x][p + y] = min(500000001LL, dp[x][p + y] + add);
      }
    }
  }

  ll pref = 0;
  for (int i = 0; i < maxnights; i++) {
    if (i == 0) {
      pref = dp[n - 1][i];
      cout << dp[n - 1][i] << "\n";
    } else {
      pref = min(500000001LL, pref + dp[n - 1][i]);
      cout << pref << "\n";
    }
  }
}

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