oj.uz

Submission #942805

# Submission time Handle Problem Language Result Execution time Memory
942805 2024-03-11T04:52:29 Z artixkrishna Journey (NOI18_journey) C++14
100 / 100
 88 ms 40060 KB 
#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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2648 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 2 ms 2652 KB Output is correct
6 Correct 2 ms 2652 KB Output is correct

Subtask #4
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2648 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 2 ms 2652 KB Output is correct
6 Correct 2 ms 2652 KB Output is correct
7 Correct 88 ms 40060 KB Output is correct
8 Correct 68 ms 25424 KB Output is correct
9 Correct 13 ms 5208 KB Output is correct
10 Correct 71 ms 6860 KB Output is correct