oj.uz

Submission #828899

# Submission time Handle Problem Language Result Execution time Memory
828899 2023-08-17T18:53:23 Z NK_ Journey (NOI18_journey) C++17
100 / 100
 53 ms 6228 KB 
// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>
 
using namespace std;
 
#define nl '\n'
#define pb push_back 
#define mp make_pair
#define f first
#define s second
#define sz(x) int(x.size())
 
template<class T> using V = vector<T>;
using vi = V<int>;
using ll = long long;
using pi = pair<int, int>;
using vpi = V<pi>;
using vl = V<ll>;
using db = double;

const int INF = 5e8 + 1;

int main() {
	cin.tie(0)->sync_with_stdio(0);

	int N, M, H; cin >> N >> M >> H;

	V<vpi> nxt(N);
	for(int i = 0; i < N - 1; i++) {
		for(int t = 0; t < H; t++) {
			int u, x; cin >> u >> x;
			if (u <= i) continue;
			nxt[i].pb(mp(u, x));
		}
	}

	V<vi> dp(N, vi(M, 0));
	dp[0][0] = 1;

	for(int u = 0; u < N; u++) {
		for(auto& e : nxt[u]) {
			auto [v, d] = e;

			int ways = 0;
			for(int x = 0; x + d < M; x++) {
				ways = min(INF, ways + dp[u][x]);
				dp[v][x + d] = min(INF, dp[v][x + d] + ways);
			}
		}
	}

	for(int x = 0; x < M; x++) cout << dp[N-1][x] << " ";
	cout << nl;

	exit(0-0);
}

Subtask #1
20.0 / 20.0

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

Subtask #2
23.0 / 23.0

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

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 340 KB Output is correct

Subtask #4
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 32 ms 5024 KB Output is correct
8 Correct 29 ms 6228 KB Output is correct
9 Correct 9 ms 1876 KB Output is correct
10 Correct 53 ms 2968 KB Output is correct