Submission #942805

#	Time	Username	Problem	Language	Result	Execution time	Memory
942805		artixkrishna	Journey (NOI18_journey)	C++14	100 / 100	88 ms	40060 KiB

journey

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mxn = 1e4 + 10, mxm = 410;
const ll inf = 5e8 + 1;

ll cnt[mxn][mxm];
ll dist[mxn];
vector<pair<int, int>> paths[mxn], rg[mxn];

int main() {
  int n, m, h;
  cin >> n >> m >> h;
  for (int i = 0; i < n - 1; i++) {
    for (int j = 0; j < h; j++) {
      int a, b;
      cin >> a >> b;
      paths[i].push_back({a, b});
      rg[i].push_back({a, b});
    }
  }
  cnt[0][0] = 1;
  for (int i = 0; i < n; i++) {
    for (auto nxt : paths[i]) {
      if (nxt.first <= i)
        continue;
      ll pre = 0;
      for (int j = 0; j + nxt.second < m; j++) {
        pre = min(pre + cnt[i][j], inf);
        cnt[nxt.first][j + nxt.second] =
            min(cnt[nxt.first][j + nxt.second] + pre, inf);
      }
    }
  }
  for (int i = 0; i < m; i++)
    cout << cnt[n - 1][i] << ' ';
}

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